验证二叉树

难度: Medium

二叉树上有 n 个节点，按从 0 到 n - 1 编号，其中节点 i 的两个子节点分别是 leftChild[i] 和 rightChild[i]。

只有所有节点能够形成且只形成一颗有效的二叉树时，返回 true；否则返回 false。

如果节点 i 没有左子节点，那么 leftChild[i] 就等于 -1。右子节点也符合该规则。

注意：节点没有值，本问题中仅仅使用节点编号。

示例 1：

输入：n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
输出：true

示例 2：

输入：n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
输出：false

示例 3：

输入：n = 2, leftChild = [1,0], rightChild = [-1,-1]
输出：false

提示：

n == leftChild.length == rightChild.length
1 <= n <= 10⁴
-1 <= leftChild[i], rightChild[i] <= n - 1

Submission

运行时间: 49 ms

内存: 17.7 MB

class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
        indeg = [0] * n
        for u in leftChild:
            if u != -1:
                indeg[u] += 1
        for u in rightChild:
            if u != -1:
                indeg[u] += 1
        
        root = -1
        for i in range(n):
            if indeg[i] == 0:
                root = i
                break
        if root == -1:
            return False

        
        seen = set([root])
        q = collections.deque([root])
        print(seen,q)

        while len(q) > 0:
            u = q.popleft()
            if leftChild[u] != -1:
                if leftChild[u] in seen:
                    return False
                seen.add(leftChild[u])
                q.append(leftChild[u])
            if rightChild[u] != -1:
                if rightChild[u] in seen:
                    return False
                seen.add(rightChild[u])
                q.append(rightChild[u])
        
        return len(seen) == n

Explain

本题的解题思路是使用广度优先搜索（BFS）来遍历整棵二叉树，同时检查是否满足二叉树的性质。首先，使用一个数组 indeg 来记录每个节点的入度（即有多少个节点指向它）。根节点的入度应该为0，其他节点的入度应该为1。如果有多个节点的入度为0或者某个节点的入度大于1，则不是有效的二叉树。接着，从根节点开始，使用队列进行BFS遍历。在遍历过程中，检查是否有环（即某个节点被重复访问），以及最后是否所有节点都被访问到。如果满足这些条件，则是一棵有效的二叉树。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
        indeg = [0] * n
        for u in leftChild:
            if u != -1:
                indeg[u] += 1
        for u in rightChild:
            if u != -1:
                indeg[u] += 1
        
        root = -1
        for i in range(n):
            if indeg[i] == 0:
                root = i
                break
        if root == -1:
            return False

        
        seen = set([root])
        q = collections.deque([root])
        print(seen,q)

        while len(q) > 0:
            u = q.popleft()
            if leftChild[u] != -1:
                if leftChild[u] in seen:
                    return False
                seen.add(leftChild[u])
                q.append(leftChild[u])
            if rightChild[u] != -1:
                if rightChild[u] in seen:
                    return False
                seen.add(rightChild[u])
                q.append(rightChild[u])
        
        return len(seen) == n

Explore

在二叉树的定义中，一个有效的二叉树只有一个根节点，这个根节点是唯一一个没有父节点的节点，因此它的入度必须是0。如果存在多个入度为0的节点，这意味着存在多个根节点，从而违背了二叉树每棵树只有一个根节点的基本性质，因此这种情况下的结构不能被认为是有效的二叉树。在算法实现中，如果发现有多个入度为0的节点，则应该返回False，表示这不是一个有效的二叉树。

在广度优先搜索(BFS)中，使用一个seen集合来记录已经访问过的节点，以避免重复访问。如果在遍历过程中发现某个子节点已经存在于seen集合中，这意味着这个子节点被多个父节点指向，或者在遍历过程中形成了环。这违背了二叉树的性质，即每个节点除根节点外只有一个父节点，且应无环。因此，如果子节点已经在seen集合中，则可以立即判断这不是一棵有效的二叉树，并返回False。

代码中通过使用seen集合来跟踪已经访问过的节点确保每个节点只被访问一次。当从队列中取出一个节点进行处理时，会检查其左右子节点是否已在seen集合中；如果未在，则添加到seen集合并加入队列继续处理。这种方法不仅避免了某个节点被重复访问，还有效防止了因环而导致的无限循环。最终，如果seen集合中的节点数量等于二叉树的总节点数，且过程中没有发现重复访问的情况，就可以确认该二叉树是有效的。

在算法中，`-1`在leftChild和rightChild数组中用来表示某个节点没有左子或右子节点。在入度计算时，代码会检查leftChild和rightChild中的每个值；如果这个值不是`-1`，则对应的节点入度增加1。这样，`-1`被有效地忽略，不会影响入度计算。在BFS遍历过程中，同样会检查子节点是否为`-1`；如果是，那么就跳过该节点，不会将其加入队列中。这种处理确保了`-1`不会对节点访问逻辑造成干扰。