题干与适用场景
给定一棵任意二叉树和其中两个不同节点 p、q。一个节点也算自己的祖先；两者的最近公共祖先 是同时包含 p、q 的最深节点。例如，若 p 本身是 q 的祖先，答案就是 p。
这道题的契约有四个关键点：树不是二叉搜索树；输入给的是节点引用而不是节点值；不同节点可以有 相同值；基础版本保证 p 和 q 都在树中。实现若偷偷按数值比较，或在存在性没有保证时仍套用 基础递归，都会在追问中出错。
a
/ \
b c
/ \ / \
d e f g
\
h在这棵树中，LCA(d, h) = b，LCA(b, h) = b，LCA(e, f) = a。目标岗位是需要掌握树遍历、 递归语义和复杂度分析的软件工程师。基础问题只做一次查询；深度失控、目标可能缺失、节点带父指针 或同一棵树有大量查询，都属于改变解法的后续约束。
面试官考察点
面试官首先会看候选人是否把“最近”翻译成可执行结构：从根到 p、q 的两条路径最后一个公共 节点就是答案。这个路径方案正确，但显式保存两条路径并非必要。更好的推导是让每棵子树报告： “这里没有目标”“这里找到了一个目标”或“这里已经找到了两个目标的汇合点”。
强回答会给递归返回值一个精确定义。在以 node 为根的子树里，函数返回：
null：子树不包含p或q；p或q：子树目前只需要把一个已找到的目标向上传递；- 其他节点：该节点已经是这棵子树内的最近公共祖先。
左右递归结果都非空时，两个目标从当前节点的不同方向汇合，当前节点就是答案。只有一侧非空时， 那一侧的结果继续向上传递。当前节点等于目标时立即返回，是因为基础契约保证另一个目标存在： 另一个目标若在其子树内，当前节点就是祖先；若在外部，当前节点也需要向上传递。
还要能指出契约陷阱。基础算法在 q 不存在时可能返回 p，所以它没有顺便验证两个目标都存在。 把存在性保证删掉后，返回值必须同时携带匹配数量。对于高度为 h、节点数为 n 的树，单次 查询最坏访问每个节点一次，时间为 O(n)，递归栈为 O(h)；倾斜树中 h = n，调用栈本身就 可能成为故障点。
回答前需要澄清的问题
- 输入是节点引用还是节点值？ 节点引用允许值重复，比较应使用
node === p。只有值唯一且
契约明确时，才可以按值定位。
- 两个目标是否保证存在且互不相同？ 基础递归依赖存在性保证。任一目标可能缺失时，要返回
匹配数量；若允许 p === q，还要明确找到一次是否足够。
- 这是普通二叉树还是二叉搜索树？ 普通树必须搜索结构；BST 可以按键的相对大小沿一条路径
下降，但重复键和引用语义会让这个捷径失效。
- 树的最大节点数和高度是多少？ 平衡树的递归深度为
O(log n)；十万个节点的链状树应考虑
显式栈和父映射，避免语言运行时栈溢出。
- 同一棵静态树要回答多少次查询？ 一次查询直接 DFS 最简单。大量查询可先计算深度和
2^k 级祖先，再把单次查询降为 O(log n)。
- 节点是否已经带 parent 指针？ 有父指针时不必从根遍历整棵树，可以对齐深度后同时向上，
或记录一条祖先链再找交点。
30 秒回答框架
“我会先确认这是普通二叉树，p、q 是节点引用且都保证存在，所以值重复不影响判断。我让递归 函数返回当前子树发现的目标或已经形成的公共祖先。空节点返回 null，当前节点是 p 或 q 时 返回自己；递归左右子树后，如果两边都非空，说明两个目标在当前节点汇合，返回当前节点，否则 返回唯一非空的一边。每个节点最多访问一次，最坏时间 O(n)，递归栈 O(h)。我会用目标互为 祖先、分处两侧、值重复和倾斜树测试。若目标可能缺失，返回值要增加匹配数；若高度不受控，就改用 显式栈建立父映射。”
分步骤深入解答
第一步：从显式路径得到正确基线
最直观的方法是分别找出根到 p 和根到 q 的路径，再从头比较，最后一个相同节点就是最近公共 祖先。它很适合先说明定义，也容易验证目标是否存在。两次 DFS 仍是 O(n) 时间，路径和递归栈 占 O(h)；若实现把搜索过的全部节点都保留，空间可能扩大到 O(n)。
路径法的冗余在于两次搜索共享大量前缀。我们真正需要的只有“一个子树向父节点报告了什么”， 因此可以把两条路径压缩为一次后序遍历。
第二步：定义返回值并写出一次遍历
interface TreeNode {
value: number
left: TreeNode | null
right: TreeNode | null
}
function lowestCommonAncestor(
root: TreeNode | null,
p: TreeNode,
q: TreeNode,
): TreeNode | null {
if (root === null || root === p || root === q) {
return root
}
const left = lowestCommonAncestor(root.left, p, q)
const right = lowestCommonAncestor(root.right, p, q)
if (left !== null && right !== null) {
return root
}
return left ?? right
}这段代码比较对象身份，不读取 value，所以两个节点同值也不会混淆。后序顺序很关键：当前节点 需要先知道左右子树各自是否返回了目标或已经找到的答案，才能判断自己是否是首次汇合点。
第三步：用不变量证明，不靠样例猜测
对任意以 node 为根的子树，假设两个递归调用都满足返回值定义。
node为空时，子树没有目标，返回null正确。node等于p或q时，返回node。因为两个目标保证存在，当前目标若包含另一个目标，
自己就是最近公共祖先；否则它需要继续向祖先报告已找到一个目标。
- 左右结果都非空时，两个目标分别由两侧报告。任何更深节点都只属于一侧，无法同时包含两者，
所以 node 是最深的共同祖先。
- 只有一侧非空时，当前节点尚未形成新的汇合点；那一侧返回的目标或答案仍是应该向上传递的
唯一有效结果。两侧都空则返回 null。
由结构归纳，根节点的返回值就是整棵树的最近公共祖先。这个证明也覆盖“p 是 q 的祖先” 这一容易漏掉的情况：遍历到 p 时直接返回 p，无需继续从其子树把 q 再返回一次。
第四步：分析真实的时间和空间
最坏情况下，函数访问 n 个节点，每个节点只做常数工作，时间为 O(n)。早期遇到目标可能少 访问部分子树，但不能把最好情况写成最坏复杂度。
辅助空间由递归深度决定，为 O(h)。平衡树中 h = O(log n)；完全倾斜时 h = n。输出只 是一个节点引用，不计入辅助空间。声明“空间 O(1)”会忽略调用栈。
第五步：目标可能缺失时改变返回契约
若 API 不保证目标存在，基础函数会误报：树中只有 p 时，它会把 p 一路传到根并返回。安全 版本必须区分“候选节点”和“实际找到几个目标”。
interface SearchResult {
candidate: TreeNode | null
matches: number
}
function lowestCommonAncestorValidated(
root: TreeNode | null,
p: TreeNode,
q: TreeNode,
): TreeNode | null {
function visit(node: TreeNode | null): SearchResult {
if (node === null) {
return { candidate: null, matches: 0 }
}
const left = visit(node.left)
if (left.matches === 2) {
return left
}
const right = visit(node.right)
if (right.matches === 2) {
return right
}
const self = node === p || node === q ? 1 : 0
const matches = left.matches + right.matches + self
return {
candidate: matches === 2 ? node : left.candidate ?? right.candidate ?? (self ? node : null),
matches,
}
}
const result = visit(root)
return result.matches === 2 ? result.candidate : null
}这里仍假设 p !== q。若允许同一引用作为两个目标，就应先单独约定：找到该节点一次即返回它， 而不能继续要求 matches === 2。约束变化必须先于代码变化。
第六步：深树用显式栈和父映射
当高度可能接近十万，递归的渐进空间没有变，但运行时调用栈可能先溢出。可以用显式栈遍历，记录 parent.get(child) = node，直到 p、q 都出现在映射中。随后把 p 到根的祖先放入集合， 从 q 向上遇到的第一个集合成员就是答案。
该方案时间仍为 O(n)，显式空间为 O(n)。它比递归占更多堆内存，却把资源从大小受限的调用栈 移到可控的数据结构。对高度有合理上限的一次查询，递归版更短、更容易证明，不必为了极端约束 默认采用父映射。
第七步：用对抗用例验证语义
至少覆盖以下用例：
| 用例 | 期望 | 捕获的问题 | |---|---|---| | p、q 分处根的两侧 | 返回根 | 只搜索一条路径 | | p 是 q 的祖先 | 返回 p | 忘记节点也是自己的祖先 | | 两节点位于同一深子树 | 返回子树内节点 | 返回了过高的公共祖先 | | 两个不同节点的 value 相同 | 按引用返回正确节点 | 错把值当身份 | | 单节点树且 p === q 的扩展契约 | 返回该节点 | 没定义相同目标 | | 一个目标缺失 | 安全版本返回 null | 基础版误报 | | 十万个节点的链 | 迭代版完成 | 递归栈溢出 |
除固定样例外，可以生成随机小树，用路径基线与一次遍历结果按节点引用比较。基线和优化方案来自 不同实现思路，能比只写几个手工断言更有效地发现错误。
高质量示范回答
“我先固定契约：这是普通二叉树，p 和 q 是不同节点的引用、都保证存在，节点值可能重复， 所以代码比较引用而不比较值。
我会做一次后序 DFS。函数对一棵子树返回 null、其中一个目标，或已经找到的最近公共祖先。 空节点返回 null，当前节点等于任一目标时返回自己。左右递归后，两边都非空说明两个目标在当前 节点首次汇合，所以返回当前节点；只有一边非空就把那边向上传递。
正确性来自这个返回值不变量。若两个目标分处左右子树，任何更深节点都不可能同时包含它们；若 一个目标是另一个的祖先，遍历到祖先目标时直接返回它也正好符合定义。最坏访问每个节点一次， 时间 O(n)，递归栈 O(h)，倾斜树时会退化为 O(n) 栈深。
我会测试分处两侧、互为祖先、同一深子树和重复值。若目标不保证存在，当前函数可能把唯一存在的 目标当答案，我会让递归额外返回匹配数，只有找到两个目标才接受候选节点。若树可能非常深，就用 显式栈建立父映射，避免调用栈溢出。”
常见错误
- 把二叉树当 BST 按值选左右 → 普通二叉树没有有序性，重复值也无法表示节点身份 →
按结构搜索并比较节点引用。
- 左右结果任一非空就返回当前节点 → 单侧只有一个目标时会把答案抬到根 → **只有两侧都非空
才返回当前节点，否则传递非空结果。**
- 认为
p必须严格在答案下面 → 一个节点也算自己的祖先，p可能就是答案 → **把当前
节点等于目标作为递归基例。**
- 在缺失节点契约下复用基础算法 → 只找到一个目标也会返回非空结果 → **同时返回匹配数量，
找到两个目标才成功。**
- 声称辅助空间
O(1)→ 递归调用栈随树高增长，倾斜树为O(n)→ **按O(h)报告，并
在深度不受控时改用显式栈。**
- 为一次查询先做二进制提升 → 预处理代码和
O(n log n)空间没有被查询量摊薄 → **单次
查询使用一次 DFS，大量查询再预处理。**
- 只测试两个叶子分处两侧 → 无法暴露祖先目标、重复值、缺失节点和深度问题 → **用契约边界
组织测试矩阵。**
追问及应对
如果 p 或 q 可能不在树中，如何保证不误报？
让递归结果包含候选节点和匹配数。基础问题中两个目标不同，因此总匹配数只有 0、1、2。 根结果为 2 才返回候选 LCA，否则返回 null。不能先运行基础算法再检查返回值是否非空，因为 唯一存在的目标本身就是非空返回值。
如果树有十万个节点且可能完全倾斜呢？
改用显式栈建立父映射。找到两个目标后，把 p 的祖先放入集合，再沿 q 的父链找第一个交点。 时间 O(n)、堆空间 O(n)，但不会消耗十万层语言调用栈。若内存约束也很紧，应进一步确认树 是否能提供 parent 指针或受控的遍历接口，而不是假设递归可用。
如果同一棵静态树要回答一百万次 LCA 查询呢？
每次 O(n) DFS 不再合适。先 DFS 计算深度和每个节点的 2^k 级祖先，预处理时间与空间均为 O(n log n)。查询时先把较深节点提升到同一深度，再从最大的 k 向下同时提升两个节点，单次 为 O(log n)。若查询量更大且实现复杂度可接受，还可评估 Euler tour 加 RMQ；选择取决于更新 频率、内存和查询延迟目标。
如果节点已经有 parent 指针，仍需要从根遍历吗？
不需要。可以先计算两节点深度，把较深者上移到同一层，再同步向上直到相等，时间为 O(h)、 额外空间 O(1)。也可以记录 p 的全部祖先，再沿 q 上移找第一个交点，代码更直接但需要 O(h) 集合空间。
如果输入是二叉搜索树，可以怎样简化？
在键唯一且按键寻找目标的契约下，若 p、q 都小于当前键就向左，都大于就向右，否则当前 节点就是分叉点或其中一个目标，时间 O(h)、迭代空间 O(1)。若节点值可重复或输入仍以引用 标识目标，必须先定义重复键放置规则和定位方式；不能仅凭两个数值安全地替代普通树算法。