LeetCode 面试题 04.08. 首个共同祖先
题目描述
题意分析
在普通二叉树中，找出同时包含
p、q且位置最深的祖先节点，答案可以就是其中一个目标。题目保证两个目标不同且都存在，并要求不额外建立保存其他节点的数据结构，不能把它当作二叉搜索树按值寻找。
解法：后序合并两侧目标信息
核心思路
[!blue]
两个目标若分布在当前节点的左右两侧，它们的路径就在这里汇合；若都在一侧，答案还应继续留在那一侧。用后序递归汇总两边找到的信息，就能定位最低的汇合处，不必建立父指针表或保存两条祖先路径。
递归返回空，表示这棵子树没有目标；只找到一个目标时返回该目标；两个目标都在子树内时，返回它们已经找到的最近公共祖先。父层只需判断两侧是否为空，并保留已有的答案节点。
当前节点就是
p或q时可以直接返回：若另一目标在其下面，当前节点自己就是最近公共祖先；若另一目标在外面，返回当前目标即可让上层继续汇合。两个目标都存在的前提保证最终不需要另做存在性检查。当前节点不是目标时，递归左右子树。若两侧都非空，两个目标分别在两边，当前节点是它们最深的共同祖先，因为任何更低的子树都只能覆盖一侧。若只有一侧非空，直接上传那一侧的结果；它可能还是单个目标，也可能已经是更深的完整答案，不能擅自换成当前节点。两侧都空时自然返回空。
解题步骤
- 空节点或目标节点直接返回。
- 递归查询左右子树。
- 一侧为空则返回另一侧，两侧非空返回当前根。
- 返回根调用得到的节点引用，不按节点值另外查找。
代码实现
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 撞到目标即上报，不再深入。
if (root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 两侧都有：当前节点即分叉点；只有一侧：把该侧结果上传。
return left == null ? right : (right == null ? left : root);
}
}
func lowestCommonAncestor(root *TreeNode, p *TreeNode, q *TreeNode) *TreeNode {
// 撞到目标即上报，不再深入。
if root == nil || root == p || root == q {
return root
}
left := lowestCommonAncestor(root.Left, p, q)
right := lowestCommonAncestor(root.Right, p, q)
// 两侧都有：当前节点即分叉点；只有一侧：把该侧结果上传。
if left == nil {
return right
}
if right == nil {
return left
}
return root
}
复杂度分析
- 时间复杂度：$O(n)$，每个被访问的节点只处理一次。
- 空间复杂度：$O(h)$，只使用递归栈，没有额外的节点集合或父指针表。
关键点总结
[!green]
两侧非空才在当前节点汇合，单侧非空则保留该侧已经找到的更低答案；这使最终返回的是最近公共祖先，而不是任意共同祖先。
易错点总结
[!yellow]
- 必须比较节点引用，不能把普通树当 BST 按值剪枝。
- 某目标是另一个目标的祖先时应返回该目标。
- 单侧为空不表示搜索失败，两个目标可能都在另一侧，应继续上传该侧结果。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 235. 二叉搜索树的最近公共祖先 | 中等 | 原题是 BST，可按值决定下降方向；本题普通树需要查询左右子树。 |
| 1123. 最深叶节点的最近公共祖先 | 中等 | 同样后序向上合并祖先信息，原题目标集合是所有最深叶子。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！