二叉树最近公共祖先：节点身份与祖先路径

1. 先确定题目契约

给定二叉树根节点 root 和两个节点对象 p、q，返回同时包含它们的最深祖先。节点可以是自己的祖先，因此 p === q 时，只要它在树中，答案就是它自己。

比较对象身份，不比较 val；不同节点可以具有相同值。
任一节点不在树中，或输入为空，返回 null。
输入是有限、无环且每个非根节点只有一个父节点的二叉树，子节点为 left/right 或空值。
若题目保证两个节点都存在，可使用递归后序算法；没有该保证时，不能找到一个节点就直接当作最终答案。

2. 父指针表与路径相交

树根为 R，P 与 Q 位于 A 的两个分支，向上追溯时第一个共同节点为 A；D 虽与 P 同值但不是同一节点

图中的字母代表节点身份，括号内是值。P.val === D.val 不影响答案：LCA(P, Q) = A，LCA(P, D) = R，LCA(A, Q) = A。

从根遍历整棵树，建立 child -> parent 映射，根的父节点记为 null。
确认 p、q 都在映射中，再把 p 到根的整条路径放进 Set。
从 q 向根走，遇到的第一个集合成员就是最近公共祖先。

function lowestCommonAncestor(root, p, q) {
  if (root == null || p == null || q == null) return null

  const parent = new Map([[root, null]])
  const stack = [root]
  while (stack.length > 0) {
    const node = stack.pop()
    for (const child of [node.left, node.right]) {
      if (child == null) continue
      if (parent.has(child)) {
        throw new TypeError('Input must be a tree without shared children or cycles')
      }
      parent.set(child, node)
      stack.push(child)
    }
  }

  if (!parent.has(p) || !parent.has(q)) return null
  const ancestors = new Set()
  for (let node = p; node !== null; node = parent.get(node)) {
    ancestors.add(node)
  }
  for (let node = q; node !== null; node = parent.get(node)) {
    if (ancestors.has(node)) return node
  }
  return null
}

在满足输入契约时，两条祖先路径至少在根相交。从 q 往上遍历的顺序就是深度递减的顺序，所以第一次相交不可能跳过一个更深的公共祖先。整个过程时间 O(n)、额外空间 O(n)；显式栈避免深树造成调用栈溢出。

3. 后序递归如何理解

若保证 p、q 都在树中，后序递归可以让左右子树分别向上返回“找到的目标或已经确定的祖先”：两边都返回非空时，当前节点就是分叉点；仅一边非空则继续向上传递。遇到 p 或 q 可以返回该节点，因为祖先允许包含自身。

这个简版的关键前提是两节点都存在。如果只有 p 存在，它仍会返回 p，因此未知存在性时应另做成员检查，或在后序状态中同时统计命中的目标身份。递归方案时间 O(n)、栈空间 O(h)，斜树中 h = n。

4. 边界与追问

情况	预期行为
空树或任一目标为空	返回 `null`
两个不同节点值相同	仍按节点身份找到公共祖先
一个目标是另一个的祖先	返回较高的目标节点
相同目标在树中 / 不在树中	返回该节点 / `null`
目标只有一个在树中	返回 `null`
存在环或共享子节点	当前实现抛出错误，不把图当作树处理

如果给的是值而不是节点？ 先约定值唯一，或明确多个匹配节点的选择规则，不能静默取第一个。如果是二叉搜索树？ 可在值唯一等条件下利用大小关系缩小搜索范围，普通二叉树没有这个性质。如果同一棵静态树要查询很多次？ 父指针和深度可以预处理，进一步可使用倍增或 Euler Tour/RMQ；发生结构变化后必须更新或重建预处理结果。

相关内容：遍历与树结构互转、二叉搜索树。