How can I use DFS to validate a binary tree structure?

By performing a DFS traversal, you can track parent relationships and detect cycles, ensuring that the structure forms a valid tree.

What is the time complexity of the solution for this problem?

The time complexity is O(n), where n is the number of nodes, due to the need to traverse the entire graph once.

Why do we need to detect the root node in this problem?

A valid binary tree must have exactly one root node, which does not appear as a child of any other node. Multiple roots indicate an invalid tree.

What common mistakes should I avoid when solving the 'Validate Binary Tree Nodes' problem?

Avoid missing cycles, incorrectly identifying root nodes, and failing to detect disconnected structures in the graph.

How can GhostInterview assist in solving graph traversal problems like this one?

GhostInterview provides step-by-step assistance in applying DFS, tracking parent-child relationships, and detecting errors in tree structures.

#1361

Medium

auto_awesome图·DFS·traversal

LeetCode 题解工作台

验证二叉树

二叉树上有 n 个节点，按从 0 到 n - 1 编号，其中节点 i 的两个子节点分别是 leftChild[i] 和 rightChild[i] 。只有所有节点能够形成且只形成一颗有效的二叉树时，返回 true ；否则返回 false 。如果节点 i 没有左子节点，那么 leftC…

树深度优先搜索广度优先搜索并查集图

题目描述

二叉树上有 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

lightbulb

解题思路

方法一：并查集

我们可以遍历每个节点 $i$ 以及对应的左右孩子 $l$ , $r$ ，用 $vis$ 数组记录节点是否有父节点：

若孩子节点已存在父节点，说明有多个父亲，不满足条件，直接返回 false。
若孩子节点与父节点已经处于同一个连通分量，说明会形成环，不满足条件，直接返回 false。
否则，进行合并，并且将 $vis$ 数组对应位置置为 true，同时将连通分量个数减去 $1$ 。

遍历结束，判断并查集中连通分量个数是否为 $1$ ，若是返回 true，否则返回 false。

时间复杂度 $O(n \times \alpha(n))$ ，空间复杂度 $O(n)$ 。其中 $n$ 为节点个数，而 $\alpha(n)$ 为阿克曼函数的反函数，即反阿克曼函数，其值小于 $5$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def validateBinaryTreeNodes(
        self, n: int, leftChild: List[int], rightChild: List[int]
    ) -> bool:
        def find(x: int) -> int:
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        p = list(range(n))
        vis = [False] * n
        for i, (a, b) in enumerate(zip(leftChild, rightChild)):
            for j in (a, b):
                if j != -1:
                    if vis[j] or find(i) == find(j):
                        return False
                    p[find(i)] = find(j)
                    vis[j] = True
                    n -= 1
        return n == 1

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Look for an understanding of tree structure properties and cycle detection.
question_mark
Check if the candidate handles edge cases like multiple roots or nodes with no parents.
question_mark
Evaluate how efficiently the candidate applies DFS and parent tracking to solve the problem.

warning

常见陷阱

外企场景

error
Failing to handle cycles correctly in the graph can lead to incorrect results.
error
Incorrectly identifying the root node, especially in cases where there is more than one root.
error
Not accounting for the scenario where nodes might not form a connected structure.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the binary tree is sparse or very large? Can your solution handle it efficiently?
arrow_right_alt
How would you handle the case where some nodes are missing their children?
arrow_right_alt
Can you modify the solution to identify the specific type of error (cycle, multiple roots, etc.)?

help

常见问题

外企场景

继续练习

#2368 受限条件下可到达节点的数目 #1377 T 秒后青蛙的位置 #1319 连通网络的操作次数