LeetCode 题解工作台
二叉树的堂兄弟节点
在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。 如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对 堂兄弟节点 。 我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。 只有与值 x 和 y 对应的节点是堂兄弟…
4
题型
5
代码语言
3
相关题
当前训练重点
简单 · 二分·树·traversal
答案摘要
我们定义一个队列 ，队列中存储的是节点和其父节点。初始时，将根节点和空节点放入队列中。 每次从队列中取出一个节点，如果该节点的值为 或 ，则记录该节点的父节点和深度。如果该节点的左右子节点不为空，则将左右子节点和该节点放入队列中。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。
我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。
只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。
示例 1：
输入：root = [1,2,3,4], x = 4, y = 3 输出：false
示例 2：
输入：root = [1,2,3,null,4,null,5], x = 5, y = 4 输出：true
示例 3：
输入：root = [1,2,3,null,4], x = 2, y = 3 输出：false
提示：
- 二叉树的节点数介于
2到100之间。 - 每个节点的值都是唯一的、范围为
1到100的整数。
解题思路
方法一：BFS
我们定义一个队列 ，队列中存储的是节点和其父节点。初始时，将根节点和空节点放入队列中。
每次从队列中取出一个节点，如果该节点的值为 或 ，则记录该节点的父节点和深度。如果该节点的左右子节点不为空，则将左右子节点和该节点放入队列中。
当队列中所有节点都处理完毕后，如果 和 的深度相同且父节点不同，则返回 ，否则返回 。
时间复杂度 ，空间复杂度 。其中 是二叉树的节点数。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
q = deque([(root, None)])
depth = 0
p1 = p2 = None
d1 = d2 = None
while q:
for _ in range(len(q)):
node, parent = q.popleft()
if node.val == x:
p1, d1 = parent, depth
elif node.val == y:
p2, d2 = parent, depth
if node.left:
q.append((node.left, node))
if node.right:
q.append((node.right, node))
depth += 1
return p1 != p2 and d1 == d2
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate understands tree traversal techniques such as DFS and BFS.
- question_mark
The candidate effectively explains the importance of tracking the parent and depth of nodes.
- question_mark
The candidate can recognize the distinction between cousins and other types of nodes in a tree.
常见陷阱
外企场景- error
Confusing cousins with sibling nodes. Cousins are at the same depth but have different parents, unlike siblings who share the same parent.
- error
Not handling edge cases where x or y might be near the root or leaf nodes.
- error
Incorrectly assuming that BFS or DFS will automatically find cousins without tracking depth and parent.
进阶变体
外企场景- arrow_right_alt
The problem could be modified to find multiple cousin pairs in a single tree traversal.
- arrow_right_alt
The tree could be unbalanced, potentially affecting traversal strategy and performance.
- arrow_right_alt
The problem could ask for the path from the root to a given node, requiring depth and parent tracking.