算法面试：如何求二叉树的最近公共祖先？

题干与适用场景

给定一棵任意二叉树和其中两个不同节点 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 为根的子树，假设两个递归调用都满足返回值定义。

1. node 为空时，子树没有目标，返回 null 正确。
2. node 等于 p 或 q 时，返回 node。因为两个目标保证存在，当前目标若包含另一个目标，

自己就是最近公共祖先；否则它需要继续向祖先报告已找到一个目标。

1. 左右结果都非空时，两个目标分别由两侧报告。任何更深节点都只属于一侧，无法同时包含两者，

所以 node 是最深的共同祖先。

1. 只有一侧非空时，当前节点尚未形成新的汇合点；那一侧返回的目标或答案仍是应该向上传递的

唯一有效结果。两侧都空则返回 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 是不同节点的引用、都保证存在，节点值可能重复， 所以代码比较引用而不比较值。

我会做一次后序 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)。若节点值可重复或输入仍以引用 标识目标，必须先定义重复键放置规则和定位方式；不能仅凭两个数值安全地替代普通树算法。