LeetCode 1361. 验证二叉树

2021-09-28 HGNULB 约 13 分钟

文章信息 6 个分类 6 个标签

分类

题目描述

✅ 1361. 验证二叉树

题意分析

有 n 个编号 0 到 n-1 的节点，用两个数组描述父子关系：leftChild[i] 是节点 i 的左孩子编号、rightChild[i] 是右孩子编号，-1 表示没有该孩子。问这 n 个节点是否恰好构成一棵二叉树。

注意输入给的是一堆孤立的父子指向，不是一棵已经成型的树。同一个编号可能被两个不同的父节点同时声明为孩子，也可能出现环，也可能整体裂成好几块——题目要问的正是这些非法结构有没有发生。

「构成一棵二叉树」这个判断可以拆成三条互相独立的必要条件，缺一不可：每个节点最多有一个父亲（否则出现共享子树，不是树而是有向无环图）；有且只有一个节点没有父亲（它是根，多个则说明有多棵树，零个则说明存在环）；从根出发能走到全部 n 个节点（否则有游离的子结构）。这三条同时成立时，n 个节点、n-1 条边、连通且无环，就是一棵树的完整定义。

「左右孩子」这一层已经由输入格式保证了——每个节点最多两个孩子是数组结构自带的，不需要额外校验。所以本题的实质是判断一张有向图是不是有根树，二叉只是外衣。

约束里 n 最大 $10^4$，每个节点的孩子编号要么是 -1 要么是合法下标，题目保证不会出现越界编号。规模是万级，线性做法绰绰有余。

边界要留意四点：n = 1 且左右孩子都是 -1 时是合法的单节点树；节点可能指向自己（自环），此时它的入度为 1，会导致找不到根；两棵独立的树会给出两个入度为 0 的节点；一个环加上一棵树的组合，环上节点入度全为 1，靠「根唯一」查不出来，必须靠最后的连通性计数兜住。

解法：入度 + BFS 判树

核心思路

先想暴力：枚举每个节点当根，从它出发深搜，看能否不重复地访问到所有 n 个节点。这在 $n = 10^4$ 下是 $O(n^2)$，勉强能过，但完全没有利用题目的结构，而且很难说清「不重复访问」到底该怎么判。

正确的切入点是入度。在这张图里，leftChild[i] 和 rightChild[i] 各贡献一条从 i 指出的边，所以某个节点 v 的入度就是「有多少个节点声称 v 是自己的孩子」。树的定义直接翻译成入度语言：除根之外每个节点入度恰好为 1，根的入度为 0。

于是校验分成三步，每一步排除一类非法结构。

第一步查「入度是否超过 1」。一旦某个节点被两个父亲同时指向，图里就出现了汇聚点，它不可能是树。这一步在统计入度的同时就能顺手判掉，发现即返回。

第二步查「入度为 0 的节点是否恰好一个」。零个说明所有节点都有父亲，n 个节点配上至少 n 条入边，必然含环；两个及以上说明至少有两个互不相连的部分，是森林而非树。

第三步从这个唯一的根做一次遍历，数一数能访问到多少节点。这一步专门捕捉「一棵合法的树 + 一个独立的环」这种组合：环上每个节点入度都是 1，环外的树有唯一的根，前两步全部通过，但环上的节点根本不在根的可达集合里。因此必须用 count == n 这一条做最终裁决。

遍历过程中维持的不变量是：队列中的每个节点都从根可达，count 等于已经出队的可达节点数。第一步已经保证每个节点最多有一个父亲，同一节点不可能由两条边重复入队；可达部分也不可能含环，否则环的入口会有两个父亲，或根本不存在来自根的入口。因此这里不需要额外的 visited 数组。

正确性说明：三步走完后，根唯一且全部节点从根可达；因此每个非根节点至少有一个父亲，再结合入度不超过 1，便得到每个非根节点恰好一个父亲。反过来，一棵二叉树显然满足这三条，所以它们既必要又充分。

也可以用并查集：把每条父子边做合并，合并前若两端已同根则说明成环，若某节点已有父亲则说明入度大于 1，最后检查分量数是否为 1。复杂度相同，但要额外维护「是否已有父亲」的数组，代码并不更短，所以这里选入度加 BFS 的写法。

解题步骤

第一趟扫描统计入度，并在累加时立刻判断是否超过 1。 遍历每个 i，若 leftChild[i] != -1 则 indeg[leftChild[i]]++，右孩子同理。把「大于 1 就返回」写在自增的同一行，好处是发现非法立刻短路，不必等全部统计完；而且这样天然覆盖了「同一个父节点的左右孩子指向同一个编号」这种自身矛盾的输入。

第二趟扫描找入度为 0 的节点，要求恰好一个。 用一个 root 变量初始化为 -1，遇到入度为 0 的节点时若 root 已被赋值就直接返回 false（多根），否则记录下来。循环结束后若 root 仍是 -1 则返回 false（无根，意味着存在环）。两个方向的检查都要写：只查多根会漏掉纯环，只查无根会漏掉森林。

从 root 开始 BFS，出队时 count++，再把左右孩子分别入队。 count 数的是根可达节点数。入度检查已经排除了重复父边，所以节点不会重复入队，无需再维护 visited。

孩子为 -1 时跳过，不要当成节点 0 处理。 -1 是「没有这个孩子」的哨兵，不能拿它访问入度数组或加入队列。

最后返回 count == n。 这是三条必要条件里的最后一条，也是唯一能识别「树 + 环」这种组合的检查。返回 true 而不做这一步，会放过大量非法输入。

以 n = 4、leftChild = [1, -1, 3, -1]、rightChild = [2, -1, -1, -1] 走一遍（正确答案是 true）。

第一趟统计入度：i = 0 的左孩子 1，indeg[1] = 1；右孩子 2，indeg[2] = 1。i = 1 左右都是 -1，跳过。i = 2 的左孩子 3，indeg[3] = 1；右孩子 -1 跳过。i = 3 全跳过。最终 indeg = [0, 1, 1, 1]，没有超过 1 的。

第二趟找根：只有 indeg[0] == 0，root = 0，唯一。

BFS：队列初始 [0]。弹出 0，count = 1，把孩子 1、2 入队；弹出 1，count = 2；弹出 2，count = 3，把孩子 3 入队；弹出 3，count = 4。队列清空后恰好访问全部节点。

count == 4 == n，返回 true。这棵树是 0 为根、左子 1、右子 2、2 的左子 3，结构合法。

再看反例 n = 4、leftChild = [1, -1, 3, -1]、rightChild = [2, 3, -1, -1]（正确答案是 false）。第一趟统计到 i = 1 的右孩子 3 时 indeg[3] 变成 1；到 i = 2 的左孩子 3 时 indeg[3] 自增为 2，大于 1，立即返回 false。节点 3 被节点 1 和节点 2 同时认作孩子，是共享子树而非树。

再看第二类反例 n = 2、leftChild = [1, 0]、rightChild = [-1, -1]（正确答案是 false）。入度统计得 indeg = [1, 1]，都没超过 1，第一步通过；第二趟找不到入度为 0 的节点，root 保持 -1，返回 false。这是一个 0 → 1 → 0 的环，靠「无根」被抓住。

最后看第三类反例 n = 6、leftChild = [1, -1, -1, 4, -1, -1]、rightChild = [2, -1, -1, 5, -1, -1]。入度为 [0, 1, 1, 0, 1, 1]，没有超过 1；但入度为 0 的节点有两个（0 和 3），在第二趟就返回 false。这是两棵各自合法的小树，靠「根唯一」被抓住。而如果把其中一棵换成环（比如再让 leftChild[4] = 3 之类构造出环），入度全为 1 且仍有唯一的根，前两步都过，只能靠最后的 count == n 判出——这就是第三步存在的意义。

代码实现

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        int[] indeg = new int[n];
        for (int i = 0; i < n; i++) {
            // 入度超过 1 说明被两个父节点共享，立即失败。
            if (leftChild[i] != -1 && ++indeg[leftChild[i]] > 1) {
                return false;
            }
            if (rightChild[i] != -1 && ++indeg[rightChild[i]] > 1) {
                return false;
            }
        }

        int root = -1;
        for (int i = 0; i < n; i++) {
            if (indeg[i] == 0) {
                // 多个入度为 0 的节点意味着森林。
                if (root != -1) {
                    return false;
                }
                root = i;
            }
        }
        // 一个入度为 0 的节点都没有，说明整图含环。
        if (root == -1) {
            return false;
        }

        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(root);
        int count = 0;

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            count++;
            int l = leftChild[cur];
            int r = rightChild[cur];
            if (l != -1) {
                queue.offer(l);
            }
            if (r != -1) {
                queue.offer(r);
            }
        }

        // 存在根可达不到的节点，说明另有独立的环或子结构。
        return count == n;
    }
}

func validateBinaryTreeNodes(n int, leftChild []int, rightChild []int) bool {
	indeg := make([]int, n)
	for i := 0; i < n; i++ {
		if leftChild[i] != -1 {
			indeg[leftChild[i]]++
			if indeg[leftChild[i]] > 1 {
				return false
			}
		}
		if rightChild[i] != -1 {
			indeg[rightChild[i]]++
			if indeg[rightChild[i]] > 1 {
				return false
			}
		}
	}

	root := -1
	for i, degree := range indeg {
		if degree == 0 {
			if root != -1 {
				return false
			}
			root = i
		}
	}
	if root == -1 {
		return false
	}

	queue := []int{root}
	for head := 0; head < len(queue); head++ {
		cur := queue[head]
		if leftChild[cur] != -1 {
			queue = append(queue, leftChild[cur])
		}
		if rightChild[cur] != -1 {
			queue = append(queue, rightChild[cur])
		}
	}
	return len(queue) == n
}

复杂度分析

时间复杂度：$O(n)$，其中 n 是节点数。统计入度扫一趟数组，找根再扫一趟，BFS 中每个节点至多入队出队各一次、每次只看左右两条边，三段都是线性且互不嵌套。边数不超过 2n，因此整体与节点数同阶。

空间复杂度：$O(n)$，入度数组和 BFS 队列都至多保存 n 个整数。入度约束已经保证节点不会重复入队，因此无需额外访问数组。

关键点总结

把「是不是二叉树」翻译成三条可独立校验的图性质：入度不超过 1、入度为 0 的节点恰好一个、根可达全部节点。三条各自排除一类非法结构（共享子树、森林或环、游离环），少写任何一条都能构造出漏判的用例。

入度是判断有根树最省事的工具：它一次扫描就能同时回答「有没有多个父亲」和「有没有根」两个问题，比建邻接表再判环轻得多。

连通性检查不能省：前两条只约束了局部的度数，无法察觉「合法树 + 独立环」这种全局非法。count == n 是唯一的兜底，也是最容易被漏掉的一步。

先验证唯一父，再省掉 visited：在入度不超过 1 的前提下，同一孩子不可能由两条边重复到达；BFS 队列长度就是可达节点数。这个简化依赖前置校验，不能脱离条件照搬。

-1 是哨兵不是编号：所有取孩子的地方都要先判 -1 再使用，否则要么越界要么污染访问集合。见到用负数表示「空」的输入格式，第一反应就该是给每次解引用配一道判断。

面试视角：面试官想听的是「树 = n 个点 + n-1 条边 + 连通 + 无环」这个定义，以及你怎么把它拆成可执行的检查。理想答法是先说三条判据、再各举一个反例说明为什么缺不得，最后才写代码。被追问「能不能用并查集」时，答「可以，合并每条父子边，合并前两端同根即成环，最后检查分量数为 1；但还需要额外数组记录每个节点是否已有父亲，代码量不比入度法少」。

BFS 与 DFS 在此完全等价：本题只做可达性计数，两者复杂度一致。选 BFS 是因为 $10^4$ 的链式退化输入下递归有爆栈风险。

易错点总结

错误写法：只检查入度不超过 1 和根唯一，省掉最后的 count == n → 用例 n = 4、leftChild = [1, -1, 3, -1]、rightChild = [-1, -1, -1, 2] 中节点 2 与 3 互相指向形成环、节点 0 是唯一的根，前两步都通过但会错误返回 true。

错误写法：只检查「入度为 0 的节点不超过一个」，不检查「至少有一个」 → 用例 n = 2、leftChild = [1, 0]、rightChild = [-1, -1] 中 root 保持 -1，随后 queue.offer(-1) 直接数组越界异常。

错误写法：只检查根唯一，不检查入度是否超过 1 → 用例 n = 4、leftChild = [1, -1, 3, -1]、rightChild = [2, 3, -1, -1] 中节点 3 有两个父亲，但根仍唯一且 BFS 能访问到全部 4 个节点（3 会被重复入队，若无 visited 拦截则 count 变成 5），判断结果与实现细节纠缠，极易误判为 true。

错误写法：取孩子时不判 -1，直接 indeg[leftChild[i]]++ → 用例 n = 1、leftChild = [-1]、rightChild = [-1] 中访问 indeg[-1] 越界异常。

错误写法：BFS 只把左孩子入队，忘了右孩子 → 用例 n = 4、leftChild = [1, -1, 3, -1]、rightChild = [2, -1, -1, -1] 中只能访问到 0 和 1，count = 2 != 4，合法输入被误判为 false。

错误写法：默认节点 0 就是根，跳过找根的一趟 → 用例 n = 2、leftChild = [-1, 0]、rightChild = [-1, -1] 中真正的根是 1，从 0 出发只能访问到自己，count = 1 != 2，合法输入被误判为 false。

错误写法：入度判断写成 indeg[x] > 2（误以为二叉树允许两个父亲） → 用例中共享子树的节点入度为 2 不会被拦下，最终 BFS 会重复访问该子树，判定结果不可靠。

错误写法：把「每个节点最多两个孩子」也当成需要校验的条件去数出度 → 输入格式本身就只给了左右两个数组，出度天然不超过 2，多写的检查恒为真，是纯粹的冗余代码。

风险写法：用递归 DFS 遍历且忽略深度 → 链式结构会产生 $10^4$ 层调用，可能触及语言运行时的栈限制；迭代 BFS 没有这个风险。

相似题目

题目	难度	考察点
207. 课程表	中等	同样用入度判有向图性质，但目标是判环而非判树，需要拓扑排序逐层削入度
210. 课程表 II	中等	在判环基础上还要输出拓扑序，出队顺序即答案
684. 冗余连接	中等	无向图版判树，多出的那条边靠并查集在合并时发现两端同根来定位
990. 等式方程的可满足性	中等	先合并全部等式再逐条校验不等式，同为「先建关系后判合法性」的两趟结构
323. 无向图中连通分量的数目	中等	只数分量不判环，是本题第三步「连通性检查」的独立练习
547. 省份数量	中等	邻接矩阵形式的连通块统计，输入格式与本题的数组形式形成对照
310. 最小高度树	中等	已知是树，要靠不断剥离度为 1 的叶子找中心，用的是无向图的度而非入度
1466. 重新规划路线	中等	树结构上讨论边的方向，需要同时建正反两向边并在遍历时区分
1245. 树的直径	中等	已知是树后求最长路径，两次 BFS 即可，重点在树的性质而非验证
331. 验证二叉树的前序序列化	中等	另一种「验证是不是二叉树」，用槽位计数代替入度，输入是字符串序列
297. 二叉树的序列化与反序列化	困难	把树与线性表示互转，空节点的哨兵处理与本题的 `-1` 语义一致
98. 验证二叉搜索树	中等	树的结构已合法，改为验证值域约束，需要上下界随递归传递
889. 从前序与后序遍历序列构造二叉树	中等	由遍历序列反推结构，考察对二叉树父子关系的另一种刻画
886. 可能的二分法	中等	同为图上的合法性判定，改用染色或扩展域并查集检测奇环