LeetCode 993. 二叉树的堂兄弟节点

2022-02-28 HGNULB 约 11 分钟

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

分类

题目描述

✅ 993. 二叉树的堂兄弟节点

题意分析

给一棵二叉树（每个节点的值互不相同）以及两个不同的值 x 和 y，判断这两个值对应的节点是不是「堂兄弟」。定义是：深度相同，但父节点不同。

定义里两个条件必须同时成立，缺一不可。深度相同但父节点相同，那是亲兄弟，不算堂兄弟；父节点不同但深度不同，也不算。所以整道题的实质是：找出 x 与 y 各自的深度和父节点，然后做两次判断。

「节点值互不相同」这条约束很重要——它保证了按值定位节点是无歧义的，可以直接拿 node.val == x 去匹配，不必处理重复值的多义性。

「深度」这个词是最强的算法信号。凡是判定条件里出现「同一层」「深度相同」，层序遍历（BFS）就天然契合，因为它按层推进，同一层的节点会被一次性处理完，无需额外记录深度数字。用 DFS 也能做，只是要显式往下传深度和父指针，代码略长。

约束里节点数不超过 100，规模极小，$O(n)$ 遍历绰绰有余，说明本题考的是定义的完整落实，不是效率。

边界要盯住三处。其一，根节点不可能是堂兄弟——它深度为 0 且没有父节点，题目也保证 x != y，所以只要有一个是根值，答案必然是 false。其二，两个值在同一层但父节点相同（亲兄弟）要返回 false，这是最典型的陷阱用例。其三，题目保证两个值都存在于树中，但代码写成「找不到就返回 false」更稳妥。

解法：BFS 分层扫描

核心思路

最直接的想法是做两次遍历，分别找到 x 和 y，各自记录深度与父节点，最后比对。这样是对的，但要么写两遍查找逻辑，要么把状态揉进一次 DFS 里往下传参，代码都不算短。

换个角度：既然判定的两个要素是「深度」和「父节点」，而层序遍历本身就是按深度组织的，那么只要在一层之内同时观察 x 和 y 是否出现，深度是否相同这件事就被遍历顺序自动回答了，根本不需要记录任何深度数字。

于是算法变成：一层一层扫，每层开始时把 xParent、yParent 两个记录清空；扫描本层每个节点时，检查它的左右孩子是不是 x 或 y，是就把当前节点记为对应的父节点。这里的关键设计是「从父节点的视角去发现孩子」——只有站在父节点上，才能顺手把父节点记下来；如果站在孩子自己身上，就拿不到父指针了（二叉树节点没有指向父亲的指针）。

一层扫完后按三种情况分流：

两个父节点都记到了：说明 x 与 y 在同一层（同为本层节点的孩子），此时只需比较父节点是否不同，直接返回结论；

只记到一个：说明另一个不在这一层，深度必然不同，直接返回 false；

一个都没记到：本层与答案无关，继续下一层。

维持的不变量是：每轮外层循环开始时，队列里恰好装着某一层的全部节点，且 xParent、yParent 均为空；本轮结束时，这两个变量准确反映了「x/y 是否是这一层节点的孩子，以及它们的父亲是谁」。清空这一步不能省——上一层遗留的记录会让本层的判定完全错乱。

注意「父节点不同」必须比较节点本身（引用/指针）而不是节点的值。虽然本题保证值互不相同，值比较也能得到正确结果，但比引用是更本质、更不依赖题目附加条件的写法。

最后，根节点因为不是任何节点的孩子，永远不会被记录成 xParent 或 yParent，所以「根不可能是堂兄弟」这条边界被结构自然覆盖，一行特判都不用写。

解题步骤

初始化队列为 [root]：BFS 的起点。为什么不需要单独记录深度：队列按层推进，深度信息被「第几轮外层循环」隐含表达。

外层循环按层推进：先取 size = queue.size()，这是当前层的节点数。为什么必须先把 size 存下来：循环体内会往队列里追加下一层的节点，若直接用 queue.size() 当条件，会把下一层也卷进本轮，分层就失效了。

每层开始清空 xParent 与 yParent：语义是「本层内是否发现了 x/y，以及它们的父亲」。为什么必须每层清空：这两个变量的判定语义严格限定在单层内，跨层残留会让「只找到一个」的分支永远触发不到。

扫描本层每个节点，检查其左右孩子：孩子非空时，先判断它的值是否等于 x 或 y，命中就把当前节点（即父亲）记下来，然后把孩子入队。为什么从父节点看孩子而不是从孩子看自己：二叉树节点没有父指针，只有站在父亲身上才能同时拿到「孩子的值」和「父亲是谁」。

为什么用 else if 串联 x 与 y 的判断：题目保证 x != y，一个孩子不可能同时是两者，else if 既表达了这个事实又省掉一次比较。

层结束后三路分流：两个父亲都非空 → 返回「两者是否不同」；恰好一个非空 → 返回 false（深度不同）；都为空 → 继续下一层。为什么「只找到一个」可以立刻断言 false：BFS 保证越靠后的层深度越大，本层找到了一个而另一个必然在更深的层（或不存在），深度不可能相同。

循环自然结束返回 false：走完全树都没同时命中，说明至少一个值不存在或不满足条件。

以 root = [1,2,3,null,4,null,5]、x = 4、y = 5 走一遍。这棵树是：根 1，左孩子 2（右孩子 4），右孩子 3（右孩子 5）。
第一层（size = 1，队列 [1]）：清空两个记录。扫描节点 1，左孩子 2 既不是 4 也不是 5，入队；右孩子 3 同理入队。层结束时两个记录都为空，继续。
第二层（size = 2，队列 [2, 3]）：清空记录。扫描节点 2：左孩子为空跳过；右孩子值为 4，命中 x，记 xParent = 节点2，入队。扫描节点 3：左孩子为空；右孩子值为 5，命中 y，记 yParent = 节点3，入队。层结束时两个都非空，比较 节点2 != 节点3 成立，返回 true。
正确——4 和 5 都在深度 2，父亲分别是 2 和 3，是堂兄弟。

再看亲兄弟的反例 root = [1,2,3,4]、x = 4、y = 3。第一层扫节点 1：左孩子 2 不命中入队；右孩子值为 3，命中 y，记 yParent = 节点1。层结束时只有 yParent 非空，立刻返回 false——因为 3 在深度 1 而 4 在深度 2，深度不同。
再看 root = [1,2,3,null,4,null,5] 改成 x = 4、y = 5 但 4、5 都挂在节点 2 下面的情形（即 [1,2,3,4,5] 中取 x = 4、y = 5）：第二层扫描节点 2 时，左孩子 4 命中 x、右孩子 5 命中 y，两个父亲都被记成节点 2；层结束时比较 节点2 != 节点2 不成立，返回 false——亲兄弟不是堂兄弟，这正是父节点判断存在的意义。

代码实现

class Solution {
    public boolean isCousins(TreeNode root, int x, int y) {
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            // 先固定本层节点数，避免把新入队的下一层卷进来。
            int size = queue.size();
            // 记录语义仅限本层，每层必须重置。
            TreeNode xParent = null;
            TreeNode yParent = null;

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    // 站在父节点上发现孩子，才能同时拿到父指针。
                    if (node.left.val == x) {
                        xParent = node;
                    } else if (node.left.val == y) {
                        yParent = node;
                    }
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    if (node.right.val == x) {
                        xParent = node;
                    } else if (node.right.val == y) {
                        yParent = node;
                    }
                    queue.offer(node.right);
                }
            }

            // 同层出现两者：只看父节点是否不同。
            if (xParent != null && yParent != null) {
                return xParent != yParent;
            }
            // 同层只出现一个：另一个深度必然不同。
            if (xParent != null || yParent != null) {
                return false;
            }
        }
        return false;
    }
}

func isCousins(root *TreeNode, x int, y int) bool {
    queue := []*TreeNode{root}

    for len(queue) > 0 {
        // 先固定本层节点数，避免把新入队的下一层卷进来。
        size := len(queue)
        // 记录语义仅限本层，每层必须重置。
        var xParent, yParent *TreeNode

        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]

            if node.Left != nil {
                // 站在父节点上发现孩子，才能同时拿到父指针。
                if node.Left.Val == x {
                    xParent = node
                } else if node.Left.Val == y {
                    yParent = node
                }
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                if node.Right.Val == x {
                    xParent = node
                } else if node.Right.Val == y {
                    yParent = node
                }
                queue = append(queue, node.Right)
            }
        }

        // 同层出现两者：只看父节点是否不同。
        if xParent != nil && yParent != nil {
            return xParent != yParent
        }
        // 同层只出现一个：另一个深度必然不同。
        if xParent != nil || yParent != nil {
            return false
        }
    }
    return false
}

复杂度分析

时间复杂度：$O(n)$。凭什么：每个节点恰好入队一次、出队一次，处理时只做常数次值比较与指针赋值；一旦在某层同时或单独命中就提前返回，实际访问量往往更少。

空间复杂度：$O(n)$。凭什么：队列在最宽的一层会同时容纳该层的全部节点，完全二叉树最后一层约有 n/2 个节点，因此上界是 $O(n)$；其余只有两个指针变量和几个标量。

关键点总结

判定条件里出现「深度相同」时，BFS 按层推进能把深度信息隐式表达出来，省掉显式的深度计数；这比 DFS 传深度参数更短，也更不容易在回溯时漏改。

二叉树节点没有父指针，凡是需要「知道某节点的父亲」的题，都要从父节点的视角去发现孩子，在那一刻把父指针记下来。

分层 BFS 的模板要点是「先固定 size 再循环」，因为循环体内会往同一个队列追加下一层；这一行写错，所有按层的逻辑都会失效。

只在单层内有意义的状态必须每层重置。判断这类变量的作用域，看它的语义句里有没有「本层」二字。

「同层只找到一个就能立刻断言失败」利用的是 BFS 的深度单调性，属于提前返回的正确性论证，值得在面试中主动说出来。

面试视角：面试官在这道简单题上考的是边界是否想全。写完后主动报三组用例——亲兄弟（同父，返回 false）、跨层（深度不同，返回 false）、根节点参与（必为 false），比多写一个 DFS 版本更有说服力；若被追问 $O(1)$ 空间，可以说改用 DFS 传 (depth, parent) 即可，空间降到树高。

易错点总结

错误写法：只判断深度相同而不判断父节点 → 用例 root = [1,2,3,4,5]、x = 4、y = 5 中两者同层但是亲兄弟，返回 true，正确答案是 false。

错误写法：只判断父节点不同而不保证同层 → 用例 root = [1,2,3,4]、x = 4、y = 3 中父亲分别是节点 2 与节点 1，确实不同，但深度分别是 2 和 1，返回 true 是错的。

错误写法：每层不重置 xParent 与 yParent → 用例 root = [1,2,3,4]、x = 4、y = 3 中第一层记下的 yParent 残留到第二层，与第二层记下的 xParent 凑成一对，误判为 true。

错误写法：外层循环条件直接用 queue.size() 而不先固定 size → 用例任意多层的树中，下一层节点会在本轮被一起处理，层的边界完全消失，跨层的两个值被当成同层。

错误写法：从孩子的视角判断，即出队后检查 node.val == x → 用例中虽然能确定深度，但拿不到父指针，只能再额外维护一张「节点 → 父亲」的映射，代码更长且容易忘记根节点的映射。

错误写法：比较父节点时用 xParent.val == yParent.val 的取反 → 本题因值互不相同而侥幸正确，但一旦题目允许重复值，两个不同的父节点可能值相同，判定就错了；比较指针本身才是稳的。

错误写法：漏掉「同层只找到一个就返回 false」的分支 → 用例 root = [1,2,3,4]、x = 4、y = 3 中第一层只找到 y 却继续往下扫，第二层又找到 x，两个变量在不同层被分别赋值（若同时又忘了重置），最终误判为 true。

错误写法：x 与 y 的判断写成两个独立的 if 且共用同一个变量 → 用例中若不慎把 yParent 写成 xParent，同一个孩子会覆盖另一个的记录，判定结果随机。

错误写法：入队前不判空，直接 queue.offer(node.left) → 用例 [1,2,3,null,4,null,5] 中空孩子入队，下一轮 node.left 解引用时空指针异常（Go 里 nil 解引用 panic）。

错误写法：为根节点单独写特判 if (root.val == x || root.val == y) return false; → 逻辑上正确但完全多余，根不是任何节点的孩子，永远不会被记录，多写的分支反而增加出错面。

错误写法：把 else if 写成两个并列 if 并假设一个孩子可能同时命中 → 题目保证 x != y，这种情况不存在；写成并列虽不致错，但暴露了对约束的忽视。

相似题目

题目	难度	考察点
102. 二叉树的层序遍历	中等	分层 BFS 的模板题，重点就是「先固定 size 再循环」这一行
104. 二叉树的最大深度	简单	只需层数计数，无需层内状态，是分层遍历最轻的应用
111. 二叉树的最小深度	简单	同样按层推进但要在首个叶子处提前返回，叶子判定是易错点
513. 找树左下角的值	中等	靠层内首元素的记录求答案，展示了另一种「层内状态」的用法
515. 在每个树行中找最大值	中等	层内维护最大值并每层重置，与本题的重置要求完全同型
863. 二叉树中所有距离为 K 的结点	中等	需要显式建立「节点 → 父亲」的映射把树当图走，是本题父指针问题的进阶
236. 二叉树的最近公共祖先	中等	同样关心两个目标节点的祖先关系，但靠后序回传而非按层扫描