LeetCode 1650. 二叉树的最近公共祖先 III
目录
题目描述
题意分析
给两个节点
p和q，求它们的最近公共祖先。与 236、1644 最大的不同是函数签名里根本没有root：拿不到树根，也就没法自顶向下遍历。作为补偿，每个节点多了一个parent指针，根节点的parent为空。少了根、多了父指针，这两件事合起来把题目彻底换了一副骨架。自顶向下的递归失去了入口，而自底向上的行走成了唯一可行的方向：从
p沿parent一路往上，会依次经过p的所有祖先，直到根；从q出发同理。于是可以把每个节点到根的路径看成一条链表：
p → p.parent → … → root → null，q → q.parent → … → root → null。两条链最终都走到同一个根，也就是说它们必然共享一段公共后缀。最近公共祖先，正是这段公共后缀的第一个节点——也就是两条链表的相交点。题目保证
p与q都存在于同一棵树中，所以相交点一定存在，不必考虑无解。但p可能是q的祖先（此时答案是p自己），p也可能就等于q（答案还是它自己），这两种退化情况必须被主逻辑自然覆盖。两条链的长度分别是两个节点的深度加一，通常不相等，这个长度差是设计算法时必须消化掉的核心难点。
解法：双指针收缩边界
核心思路
沿
parent从节点走到根，会得到一条单链。p链和q链从最近公共祖先开始共享同一后缀，所以问题与“相交链表”完全相同；难点只是两条链在公共后缀前的长度不同。令指针
a从p出发，走到空后改从q出发；b对称地从q出发，走到空后改从p出发。这样a依次走过p链和q链，b依次走过q链和p链，两者总路程相同，起点到公共后缀的长度差被自动抵消。循环不变量是两个指针始终走过相同步数。换链后，它们在各自第二段路径中拥有相同的剩余距离，因此会在公共后缀的第一个节点相遇；该节点正是最近公共祖先。题目保证两点属于同一棵树，所以一定存在这个非空交点。
p == q时零步相遇；一方是另一方祖先时，也会在祖先节点相遇，无需特判。
解题步骤
- 初始化
a = p、b = q，节点自身也可能是答案。- 当
a != b时同步推进两个指针。- 指针非空就走到
parent；为空就切换到另一个指针的起点。- 两者相同时返回该节点。
例如
p = 5、q = 4，且 5 是 4 的祖先。两条父链长度不同，但换链后都会走过两条链，最终在节点 5 相遇。比较必须使用节点引用。即使节点值可能相同，也不代表它们是同一个祖先节点。
代码实现
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)$，两个指针至多各走完两条父链；最坏可写为 $O(h)$，其中 $h$ 是树高。
- 空间复杂度：$O(1)$，只使用两个节点指针。
关键点总结
- 父指针把“节点到根”变成链表，LCA 就是两条链的第一个公共节点。
- 换链让两个指针各走一遍两条路径，自动抵消深度差。
- 空指针时必须切换到对方起点，而不是对方父节点。
- 使用引用相等判断节点，不能比较
val。p == q和祖先包含关系都由同一循环自然覆盖。
易错点总结
- 从
p.parent、q.parent开始会跳过节点自身；当p是答案时会返回更高祖先。- 换链时回到自己的起点，无法抵消长度差，可能永不相遇。
- 换到对方的
parent会让两条拼接路径长度再次错位。- 比较节点值而非引用，会在不同但同值的节点上提前停止。
- 两个指针必须每轮各前进一步，否则“已走步数相同”的不变量失效。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 160. 相交链表 | 简单 | 与本题完全同构，把父指针换成 next，双指针换链的原型就在这里 |
| 236. 二叉树的最近公共祖先 | 中等 | 有根无父指针，只能自顶向下后序递归，空间是 $O(h)$ 的调用栈 |
| 235. 二叉搜索树的最近公共祖先 | 中等 | 借助有序性一路比大小下探，迭代实现同样能做到 $O(1)$ 空间但方向相反 |
| 1644. 二叉树的最近公共祖先 II | 中等 | 目标可能不存在，必须走完全树统计存在性，不能提前返回 |
| 1676. 二叉树的最近公共祖先 IV | 中等 | 目标扩展成一组节点，用集合判定命中，递归骨架与 236 一致 |
| 142. 环形链表 II | 中等 | 同样是常数空间的双指针，但靠快慢速度差而非路径长度对齐，推导方式完全不同 |
| 1483. 树节点的第 K 个祖先 | 困难 | 沿父链上跳的加速版，用倍增表把单次上跳 $O(h)$ 降到 $O(\log h)$ |
| 面试题 02.07. 链表相交 | 简单 | 与 160 同题，可直接套用换链写法，常被拿来和本题对照提问 |