LeetCode 1361. 验证二叉树

约 6 分钟
文章信息 6 个分类 6 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 字节
标签
深度优先搜索 树 广度优先搜索 二叉树 图 并查集

题目描述

✅ 1361. 验证二叉树

image-20260929080515968

image-20260929080516114

image-20260929080516191

题意分析

节点编号为 0..n-1，两个数组分别给出每个节点的左、右孩子编号，负一表示该孩子不存在。判断这些关系是否将全部 n 个节点恰好组成一棵合法二叉树。

输入只是候选关系，并不保证已经是树：可能一个孩子被引用多次、存在环，或分成互不连通的部分。二叉限制每个节点最多两个孩子，而不是允许一个节点有两个父节点；根也不一定是编号零。

解法：入度 + BFS 判树

核心思路

[!blue]

合法有根树需要三个条件：根没有父引用，其余节点各有一个父引用，而且从根能到达全部节点。左右孩子数组已经限制了每个节点最多两个孩子，接下来只需验证父引用和整体连接关系。

先统计入度，也就是每个节点被当作孩子引用的次数。只要大于一就失败，即使两次引用来自同一个父节点的左右位置也不行。再寻找入度为零的节点，必须恰好有一个，才能作为唯一根；没有根或有多个根都不能构成单棵树。

这些检查仍不能排除与根无关的独立环，因为环上每个节点的入度也可以恰好为一。因此还要从唯一根遍历，确认可达节点数等于 n，不能在找到唯一根后直接成功。

在前面已保证入度至多一、根入度为零的前提下，根可达部分不会出现重复访问：两条不同路径汇入同一节点需要两个父引用；若从根进入一个环，第一个入环节点既有环内前驱又有环外前驱，同样超过一，根自身则不能在环中。因此这份 BFS 无需额外 visited，计数不会因可达环而无限增长。

若遍历覆盖全部节点，唯一根、单一父引用和无可达环就共同保证整张结构是一棵二叉树；若未覆盖，剩余节点构成独立结构，必须拒绝。

解题步骤

  1. 扫描所有左右孩子，跳过负一，每次增加对应入度，超过一立即返回假。
  2. 找到唯一入度为零的节点，多于一个或一个也没有都返回假。
  3. 从该根做 BFS，遇到非空孩子就入队，并统计处理的节点总数。
  4. 仅当可达数量等于 n 时返回真。

代码实现

class Solution {
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        int[] indeg = new int[n];

        for (int i = 0; i < n; i++) {
            // 同一孩子被重复引用，不能构成树。
            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) {
                // 出现多个候选根，不能构成单棵树。
                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)$，统计入度、找根和遍历各为线性。
  • 空间复杂度：$O(n)$，保存入度和遍历队列。

关键点总结

[!green]

  • 统计的是父引用次数，同一父节点两次指向同一孩子也不合法。
  • 根唯一只是必要条件，独立环可能通过入度检查，仍需验证全部节点可达。
  • 不使用 visited 依赖前面的入度与根检查，不能把这段遍历直接用于任意有向图。
  • 孩子为负一表示缺失，不是可以访问的节点编号。

易错点总结

[!yellow]

  • 假设节点 0 一定是根：输入的真实根可能是其他编号。
  • 不检查连通性：会放过独立环与合法树并存的情况。
  • 二叉理解成最多两个父节点：二叉限制孩子数，每个非根仍只能一个父节点。
  • 忽略 -1 哨兵：会访问非法下标。

相似题目

题目 难度 关联与区别
261. 以图判树 中等 原题无向图检查连通与环即可，本题还需检查每个节点至多一个父亲并且根唯一。
685. 冗余连接 II 困难 同样涉及有向树中的入度冲突和环，本题判断一般给定结构，原题只移除一条多余边。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/47879271
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！