LeetCode 1650. 二叉树的最近公共祖先 III
题目描述
题意分析
两个目标节点属于同一棵树，节点带有
parent指针，接口没有给出根节点。沿父指针可以直接访问所有祖先，目标节点自身也应包含在候选中。
解法：父链双指针换头
核心思路
[!blue]
从p、q分别沿parent走到根，就得到两条链。一旦经过同一个节点，后续父节点也完全相同，因此两条链共享一个后缀。这个公共后缀的第一个节点，就是从下向上遇到的最近公共祖先。两个指针分别从
p、q出发，每轮都前进一步。非空时移到父节点，走到空后则切换到对方的起点。这样较短父链的指针会先换头，之后双方都补走另一条链的独有部分，消除起始深度差。设两条链在公共后缀之前分别有 $a$、$b$ 个节点，公共后缀有 $c$ 个节点。若此前还没有相遇，换头后到达公共后缀起点，两个指针分别走了 $a+c+1+b$ 和 $b+c+1+a$ 步，其中 $1$ 是从空指针切换到另一链起点的一步。总步数相同，因此会同时到达最近公共祖先。
比较的是节点身份，首次相等就返回。若两个目标相同，循环一开始就结束；若其中一个是另一个的祖先，起点也保留在父链中，不会漏掉它。
解题步骤
- 初始化两个指针为 p、q。
- 指针不同就同步推进。
- 非空指针走向父节点，空指针切换到对方起点。
- 相遇时返回该节点。
代码实现
class Solution {
public Node lowestCommonAncestor(Node p, Node q) {
Node a = p;
Node b = q;
while (a != b) {
// 走空后切换到对方起点，抵消两条父链的长度差。
a = a == null ? q : a.parent;
b = b == null ? p : b.parent;
}
return a;
}
}
func lowestCommonAncestor(p *Node, q *Node) *Node {
a, b := p, q
for a != b {
// 走空后切换到对方起点，抵消两条父链的长度差。
if a == nil {
a = q
} else {
a = a.Parent
}
if b == nil {
b = p
} else {
b = b.Parent
}
}
return a
}
复杂度分析
- 时间复杂度：$O(h_p+h_q+1)$，$h_p$、$h_q$ 为两点到根的路径长度，每个指针至多走过两条父链。
- 空间复杂度：$O(1)$，只使用两个指针。
关键点总结
[!green]
- 最近公共祖先对应父链的第一个交点。
- 换头抵消深度差，无需单独计算深度。
- 节点自身也可能是祖先，起点必须包含自身。
易错点总结
[!yellow]
- 从 parent 开始：可能跳过正确答案。
- 走空后回到自己的起点：没有补齐另一条链的长度差。
- 两指针推进次数不一致：破坏同步行走的前提。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 160. 相交链表 | 简单 | 沿parent向上就是两条最终相交的链，链表相交的双指针切换写法可直接用于寻找共同祖先。 |
| 236. 二叉树的最近公共祖先 | 中等 | 普通LCA从根往下查，本题已有父指针，可以直接比较两条祖先链。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！