031 · Cousins in Binary Tree

algorithm

Published

June 8, 2026

My First Thoughts

这道题挺有意思的。

实际需要解决 3 个问题：

在一棵树上找到 x、y
判断 x、y 在同一层
判断 x、y 并非来自同一个父节点

对吧，这是核心的 3 个问题。

我首先想到的是用个字典。和之前 deque 一样，我可以按层走，字典记录下每层的键值对：键是每层节点的 val，值是父节点的值。这样第三点“父节点不同”就可以通过字典里的值来判断。

实现起来大概就是：当前层走过时，把每个节点的左右孩子加入记录，孩子的值作为 key，当前节点作为 parent。这个方向应该是 ok 的，只是效率未必最高，因为我们可能记录了这一层所有节点，但最后真正关心的只有 x 和 y。

更直接的判断是，在经过父节点时直接看它的两个子节点是不是刚好一个等于 x、一个等于 y：

node.left.val, node.right.val == x, y

或者反过来：

node.left.val, node.right.val == y, x

如果这种情况成立，说明 x 和 y 是同一个父节点的两个孩子，那它们肯定不是堂兄弟节点。

然后代码可以从队列开始：

queue = deque([root])

while queue:
    for _ in range(n):
        node = queue.popleft()

        if node.val != x and node.val != y:
            if node.left:
                ...

这里已经抓到了最关键的方向：这题天然适合一层一层地看，因为“是不是同一层”本来就是题目条件之一。

Why That Is Not Enough

字典方案是能做的，但可以再收紧一点。

题目只问 x 和 y 这两个节点是不是堂兄弟，并不需要保存每一层所有节点的父节点。对于某一层来说，我们只需要知道两件事：

这一层有没有出现 x，如果出现了，它的父节点是谁
这一层有没有出现 y，如果出现了，它的父节点是谁

所以不一定要建一个完整的 level = {child_val: parent_val}。每层只放两个变量，比如 parent_x 和 parent_y，就够了。

另外，“检查同一个父节点的左右孩子是不是 x 和 y”这个想法能发现一种失败情况，但它不能单独完成整道题。因为堂兄弟节点的判断不仅要排除“同父节点”，还要确认“同一层”。比如：

如果 x = 4，y = 3，它们父节点不同，但深度不同，所以仍然不是堂兄弟节点。只看父节点关系不够，必须把“同层”也一起处理。

因此最终解法可以保留队列按层遍历的思路，但不需要完整字典；在每一层里只记录 x 和 y 各自的父节点。

Final Idea

关键思路是：

用 BFS 一层一层遍历；每一层开始时清空 parent_x 和 parent_y，这一层结束后再判断它们是否都出现，并且父节点是否不同。

队列里不只放节点本身，还放它的父节点：

queue = deque([(root, None)])

这里 (root, None) 的意思是：根节点没有父节点。

每进入一层之前，先记下这一层有多少个节点：

level_size = len(queue)

然后只处理这 level_size 个节点。处理时，如果当前节点值等于 x，就记录它的父节点；如果等于 y，也记录它的父节点：

if node.val == x:
    parent_x = parent
if node.val == y:
    parent_y = parent

这一层处理完后，有三种情况：

parent_x 和 parent_y 都找到了：说明 x 和 y 在同一层，只要比较父节点是否不同
只找到了其中一个：说明另一个不在这一层，深度不同，直接返回 False
两个都没找到：继续下一层

这样，“同层”由 BFS 的每轮边界保证，“不同父节点”由 parent_x != parent_y 保证。

Why It Works

BFS 每一轮只处理当前层的节点。因为每轮开始时先固定 level_size = len(queue)，后面即使把下一层的孩子加入队列，也不会在这一轮处理它们。所以在同一轮里发现的节点，一定处在同一层。

对于某一层，如果同时找到了 x 和 y，那它们已经满足“同一层”这个条件。接下来只需要比较记录下来的父节点：如果 parent_x != parent_y，它们来自不同父节点，就是堂兄弟节点；如果父节点相同，就不是。

如果某一层只找到了 x 或只找到了 y，那另一个节点不在这一层。由于题目保证 x 和 y 都存在，另一个要么在更浅层已经错过，要么在更深层还没到。无论哪种情况，它们都不可能同层，所以可以直接返回 False。

如果这一层两个都没有，就继续看下一层。最终一定会遇到其中一个或两个，因为题目保证它们都存在于树中。

Code

from collections import deque

def isCousins(root, x, y):
    queue = deque([(root, None)])

    while queue:
        level_size = len(queue)
        parent_x = None
        parent_y = None

        for _ in range(level_size):
            node, parent = queue.popleft()

            if node.val == x:
                parent_x = parent
            if node.val == y:
                parent_y = parent

            if node.left:
                queue.append((node.left, node))
            if node.right:
                queue.append((node.right, node))

        if parent_x is not None and parent_y is not None:
            return parent_x != parent_y

        if parent_x is not None or parent_y is not None:
            return False

    return False

这里比较的是父节点对象本身。因为每个树节点都是独立对象，两个节点的父节点是不是同一个，可以直接用对象比较表达出来。

Complexity

Time	\(O(n)\) - 最坏情况下需要遍历整棵树，每个节点最多入队、出队一次
Space	\(O(w)\) - 队列里最多保存一整层节点，`w` 是树的最大宽度，最坏情况下可以到 \(O(n)\)

Takeaway

遇到“同一层 + 某个额外条件”的二叉树题，先考虑 BFS。每轮开始固定队列长度，就能把一层和下一层清楚分开；然后在这一层内部只记录题目真正关心的状态。这里不需要保存整层所有父节点，只要保存 x 和 y 各自的父节点，就足够判断它们是不是堂兄弟节点。

← Quiz