LeetCode 面试题 04.08. 首个共同祖先
目录
题目描述
题意分析
给定一棵二叉树和树中的两个节点
p、q，返回它们最靠近的那个共同祖先。所谓共同祖先，是指以它为根的子树同时包含p和q；「最靠近」即在所有这样的节点中取深度最大的一个。两条前提必须先读准：节点不含父指针，所以无法从
p往上走；p与q一定存在于树中，所以不需要考虑「找不到」的返回值语义。这两条合起来把解法限定在「自顶向下遍历、自底向上汇报」的形态上。题面还特意声明一个节点可以是自己的祖先。这句话决定了当
q落在p的子树里时答案就是p本身，而不是p的父节点——这是本题最容易被写漏的一种情况。树是普通二叉树而非二叉搜索树，节点值也不保证有序甚至不保证互异，所以不能靠比较值来决定往哪边走，只能两侧都搜。边界：
p与q可能相邻、可能一个是另一个的祖先、也可能分别在根的两侧。
解法：深度优先搜索
核心思路
朴素做法是先各求一条从根到
p、到q的路径，再比较两条路径的最后一个公共节点。它正确且易懂，代价是要额外存两条路径、还要走两趟搜索。瓶颈在于路径信息其实只在「分叉点」那一处才被真正用到，其余全是冗余。换个提问方式：与其问「路径长什么样」，不如让每个节点回答一个更小的问题——在以我为根的子树里，能找到
p或q吗？找到了就把找到的那个报上去。这个问题的答案可以从孩子的答案合成，于是一趟后序遍历就够了。把返回值的语义严格定义清楚，是这段短代码能成立的全部关键：
dfs(x)返回「以x为根的子树中，p与q的最近公共祖先；若子树中只出现了其中一个，就返回那一个；两个都没出现则返回空」。这三种情况被压进同一个返回值里，才让上层能用统一的方式合并。合并规则由此自然推出：设
left = dfs(x.left)、right = dfs(x.right)。两者都非空，说明p与q分居x的两侧，x就是最近公共祖先，返回x；只有一侧非空，说明两个目标（或唯一找到的那个）都在该侧，把该侧结果原样上传即可；两侧都空则返回空。递归基
x == null || x == p || x == q里的后两项正是「一个节点可以是自己的祖先」的落地：一旦撞到目标就立即返回它、不再往下找。这样做不会漏解——若另一个目标就藏在下面，上层会看到「这一侧非空、另一侧为空」，从而把当前这个目标继续上传，最终答案正是它本身。
解题步骤
- 递归基三合一：
root == null返回空表示这一侧什么都没找到；root == p或root == q直接返回root，把「撞到目标」当作一次成功上报。用引用比较而不是值比较，因为题目给的是节点对象且值可能重复。- 先左后右各搜一次：
left = dfs(root.left)、right = dfs(root.right)。两侧都必须搜，不能因为左侧已有结果就跳过右侧——只搜一侧就无法判断两个目标是否分居两侧。- 合并三分支：
left为空返回right（要么右侧有结果，要么两侧皆空返回空，一行覆盖两种情况）；right为空返回left；两者皆非空返回root。这三行没有任何一处可以省略。- 入口无需特判：题目保证
p、q在树中，所以根调用一定会返回非空节点，不必在外层再包一层判断。以经典树
[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]走一遍，即根 3 的左孩子是 5、右孩子是 1；5 的孩子是 6 和 2，2 的孩子是 7 和 4；1 的孩子是 0 和 8。先看
p = 5、q = 1：从根 3 出发，左侧递归立刻撞到 5，返回节点 5，不再深入；右侧递归撞到 1，返回节点 1。回到根，两侧皆非空，返回根 3。答案是 3，符合直觉——5 和 1 分居根的两侧。再看
p = 5、q = 4：根 3 的右子树里递归到 1、0、8 都不是目标，全部返回空，右侧结果为空；左侧递归到 5 时命中递归基，直接返回 5，并不会继续深入去找子树里的 4。回到根，左非空右为空，返回左侧结果 5。答案是 5，正是「节点可以是自己的祖先」这条规则的体现；即便递归提前在 5 处停下没找到 4，结论依然正确，因为 4 一定在 5 的子树里，5 就是最近公共祖先。
代码实现
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)$，
n为节点数。每个节点最多被访问一次，节点内部只做常数次引用比较；命中目标时提前返回只会让访问量更少。- 空间复杂度：$O(h)$，
h为树高，全部来自递归调用栈，没有额外的路径数组或哈希表。树退化成链时为 $O(n)$。
关键点总结
- 这段代码之所以短，是因为返回值同时表达了三种含义：分叉点、唯一找到的目标、什么都没找到；写树形递归时先把返回值语义用一句话钉死，代码几乎就自己写出来了。
- 「撞到目标立即返回、不再深入」之所以不漏解，靠的是「另一个目标若在其下方，当前节点必然就是答案」这条推理；面试时必须能主动解释这一步，否则会被追问到卡壳。
- 一侧为空就上传另一侧，这一行同时覆盖了「结果在该侧」和「两侧皆空」两种情况，是把分支数从四降到三的技巧。
- 用引用比较而不是值比较：普通二叉树的节点值可能重复，按值判断会在重复值的树上返回错误节点。
- 面试常见的两个追问要预备好答案：若节点带父指针，可以像求两条链表交点那样从两侧同时上溯；若
p、q不保证存在（见 1644 题），必须改成完整搜索并额外记录两个目标各自是否被找到，不能再提前返回。
易错点总结
- 用值比较代替引用比较：树中存在两个值同为 5 的节点，
p指向深处那个 → 递归在浅处的同值节点就提前返回，得到的祖先偏高。- 左侧找到就不搜右侧：
p = 5、q = 1的经典树 → 根的左侧返回 5 后直接上传，答案变成 5 而不是 3。- 递归基漏掉
root == p与root == q：p = 5、q = 4→ 5 这一侧继续深入只找到 4，返回 4，最终答案变成 4，丢掉了「自己可以是自己祖先」的情况。- 两侧皆非空时返回
left或right而不是root：p = 6、q = 2→ 应返回它们的父节点 5，却返回了 6，答案偏低。- 合并顺序写反成「
left非空就直接返回left」：p = 6、q = 2→ 左侧返回 6 即被上传，右侧的 2 根本没机会参与合并，同样漏掉分叉点。- 把递归基里的空判去掉：任意叶子节点 → 递归到空孩子时访问
root.left直接空指针异常。- 误以为可以按二叉搜索树的方式剪枝：
[3, 5, 1]这类无序树里按值大小只往一侧走 → 目标在另一侧时直接搜不到，返回空。- 想当然地对不存在的节点也返回结果：若把本题解法照搬到「
p不在树中」的变体，p缺席时会把q当成答案返回，而正确答案应是空。- 改成迭代写法时忘了记录父节点映射：只用栈遍历而不存
child → parent的映射，回溯阶段无法上溯，最终仍要退回递归。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 236. 二叉树的最近公共祖先 | 中等 | 与本题同题，是这套后序合并模板的原型 |
| 235. 二叉搜索树的最近公共祖先 | 中等 | 有序性让分叉点可由值域判断，一路单向下探即可，无需两侧都搜 |
| 1644. 二叉树的最近公共祖先 II | 中等 | 节点不保证存在，必须走满全树并额外标记两个目标是否真的找到 |
| 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 | 简单 | 与 235 同题，迭代写法只需一个 while 循环 |
| 剑指 Offer 68 - II. 二叉树的最近公共祖先 | 简单 | 与本题同题，可直接套用 |
| 面试题 04.10. 检查子树 | 中等 | 同为「主树遍历 + 子问题判定」的双层递归，判定的是结构相等而非归属 |
| 543. 二叉树的直径 | 简单 | 同样在后序里合并左右结果，但合并出的是长度而非节点 |