父节点数组是否是一棵树：单根、合法索引、全部可达

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 每个parent[i]为−1或合法节点索引；−1代表根。空数组按本文合同不是树。
• 每节点恰有数组给定的一个父亲；不能有自环或其他环。

解题路线

1. 先检查类型与索引，再要求恰好一个−1。根据父数组构建children。
2. 从唯一根遍历。如果出现重复访问则非法；最终访问数必须n。父数组中每非根只有一个父指针，未被访问的组件必然包含环。
3. 单根加全可达足以证明树：n−1父边、所有点连通且每点唯一路径。示例重复检查作为防御，不用错误地以“根存在”结束。

手动走一遍

[−1,0,1]有效。 [−1,2,1]虽单根，但1↔2成环且根无法到达，因此无效。[−1,−1]多个根无效；[0]没有根，自环无效。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def is_tree(parent):
    n = len(parent)
    if not n or any(type(p) is not int or p < -1 or p >= n for p in parent):
        return False
    roots = [i for i, p in enumerate(parent) if p == -1]
    if len(roots) != 1:
        return False
    children = [[] for _ in parent]
    for i, p in enumerate(parent):
        if p != -1:
            children[p].append(i)
    todo, seen = [roots[0]], set()
    while todo:
        u = todo.pop()
        if u in seen:
            return False
        seen.add(u)
        todo.extend(children[u])
    return len(seen) == n

复杂度

O(n)时间、O(n)空间；可改色标沿parent链检查达到O(n)但仍需状态数组。

易错点与追问

容易失分的边界

• 不要仅计n−1条边：环与断连可同时存在。
• Python bool是int子类，示例type(p) is int避免把True误当节点1。

继续深挖

• 如果允许森林，应把“单根”换成什么条件？
• 返回具体环或未达组件，怎样保存路径位置并重建证据？