LeetCode 993. 二叉树的堂兄弟节点
题目描述
题意分析
判断值为
x、y的两个节点是否同时满足“深度相同”和“父节点不同”。同一父节点的两个孩子是兄弟节点，即使同层也不能算堂兄弟。题目保证节点值唯一，
x、y不同且都存在，可以直接按值识别目标。层序遍历负责确认深度，再记录各自父节点即可完成判断。
解法：层序遍历记录父节点
核心思路
[!blue]
队列在每轮开始时保存当前层节点。先固定
size = queue.size()，只弹出这size个节点；遍历中加入队列的孩子留到下一轮处理。这样就不会把当前层与下一层混在一起。代码站在父节点处检查左右孩子。当前层所有节点深度相同，它们的孩子也都位于同一深度；发现目标孩子时，把当前节点记录到
xParent或yParent。这两个变量每轮重新置空，只代表同一个孩子层中的发现结果。必须等整层扫描完再判断，因为另一个目标可能是本层后面某个节点的孩子。两个父节点都非空时，目标已经确认同层，只需比较父节点是否为同一个对象；只有一个非空时，该层只有一个目标，另一个目标深度必然不同，可以立即返回
false；都为空才继续搜索下一层。每个非根节点只会作为自己唯一父节点的孩子被检查一次，因此这种方式不会遗漏目标，也不会把不同深度的发现拼在一起。根节点没有父节点，且深度零只有它一个节点，涉及根的两个不同节点不可能成为堂兄弟，当前搜索会自然返回
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(w)$，w 为树的最大层宽，上界为 $O(n)$。
关键点总结
[!green]
- 同层与不同父节点两个条件必须同时成立。
- 从父节点检查孩子，可直接取得父节点身份。
- 固定层大小，避免把下一层混入当前层。
易错点总结
[!yellow]
- 只比较父节点不同：不同深度的节点也可能父节点不同。
- 同层找到两者就直接返回 true：还需要排除亲兄弟。
- 循环中使用不断变化的队列长度作为本层大小：层边界失效。
- 孩子为空仍入队并读取：后续会访问空节点。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 102. 二叉树的层序遍历 | 中等 | 分层BFS可检查两个节点是否同层，再单独比较它们是否同父。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！