怎样求二叉树的最近公共祖先？二叉搜索树有什么更简单的做法？

简答

最近公共祖先就是树里离 p、q 最近、同时把它们都包含在自己子树里的那个节点，节点也算自己的后代。比如组织架构图里，两个员工的最近公共祖先就是同时管着他俩的、级别最低的那位领导；如果其中一个人就是另一个人的上级，答案就是这个上级本人。

普通二叉树用后序递归。函数的意思是“在这棵子树里找 p 或 q”：遇到空节点、p 或 q 就直接返回当前节点。否则先问左子树、再问右子树，两边都带回了结果，说明 p、q 分在当前节点两侧，当前节点就是答案；只有一边有结果，就把那一边的结果原样往上交。

二叉搜索树每个节点左边都比它小、右边都比它大，所以从根往下走就行：p、q 都比当前值小，答案在左子树；都比它大就在右子树；一个不大于、一个不小于，说明它们在这里分叉，当前节点就是答案。

要注意，普通二叉树的写法依赖题目保证 p、q 都在树里，如果 q 不存在，函数会直接返回 p，不能当成“找到了公共祖先”。普通二叉树是 O(n)，二叉搜索树是 O(h)，h 是树高，树退化成一条链时也是 O(n)。

两种写法

fromLevelOrder 按 LeetCode 的层序数组建树，null 表示空位。看 lowestCommonAncestor 里什么时候返回 root，什么时候返回某一边的结果。

JavaScript

function fromLevelOrder(values) {
  if (values.length === 0 || values[0] === null) return null;
  const root = { val: values[0], left: null, right: null };
  const queue = [root];
  let i = 1;
  for (let head = 0; i < values.length; head++) {
    const node = queue[head];
    for (const side of ['left', 'right']) {
      if (i < values.length && values[i] !== null) {
        node[side] = { val: values[i], left: null, right: null };
        queue.push(node[side]);
      }
      i++;
    }
  }
  return root;
}

function find(root, val) {
  if (!root || root.val === val) return root;
  return find(root.left, val) ?? find(root.right, val);
}

function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left ?? right;
}

function lowestCommonAncestorBST(root, p, q) {
  let node = root;
  while (node) {
    if (p.val < node.val && q.val < node.val) node = node.left;
    else if (p.val > node.val && q.val > node.val) node = node.right;
    else return node;
  }
  return null;
}

const tree = fromLevelOrder([3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]);
const lca = (a, b) => lowestCommonAncestor(tree, find(tree, a), find(tree, b)).val;
console.log(lca(5, 1)); // 3
console.log(lca(5, 4)); // 5
console.log(lca(7, 8)); // 3

const bst = fromLevelOrder([6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]);
const lcaBST = (a, b) => lowestCommonAncestorBST(bst, find(bst, a), find(bst, b)).val;
console.log(lcaBST(2, 8)); // 6
console.log(lcaBST(2, 4)); // 2
console.log(lcaBST(3, 5)); // 4

第二个例子里 4 在 5 的子树中。递归走到 5 时直接返回 5，不再往下找 4，可是答案仍然对：3 的右子树里没有 p 也没有 q，返回 null，于是 3 把左边带回的 5 往上交，最后结果就是 5。这里能省掉往下找，正是因为题目保证 p、q 都在树里，找到其中一个、另一个又不在别的分支，那它只能在这个节点下面。

为什么两边都有结果时当前节点就是“最近”的？递归是后序的，先处理完子树才轮到当前节点。p、q 分在左右两边时，再往下走任何一边都只能包含其中一个，所以当前节点是满足条件的最深节点；往上的祖先收到的只有一边结果，会把它原样传上去，不会覆盖。

二叉搜索树为什么能直接往下走

二叉搜索树的规则是左子树所有值都比节点小，右子树所有值都比节点大。p、q 都比当前值小，它们只可能在左子树里，当前节点和右子树都可以排除。一旦 p、q 落在当前值的两侧，或者其中一个就等于当前值，它们就从这个节点开始分开了，再往下任何一边都装不下两者。所以每层只走一步，时间是 O(h)，额外空间 O(1)。这个写法假设节点值互不相同，LeetCode 235 的约束里写明了这一点。

常见追问

如果 p 或 q 可能不在树里怎么办？

递归时额外记下 p、q 各自有没有真的遇到过，并且遇到 p 或 q 以后还要继续搜它的子树，不能提前返回。最后两个都遇到过才返回结果，否则返回 null。

节点有指向父节点的指针时怎么做？

这就变成了两条链表求第一个交点。从 p 往上把祖先都放进 Set，再从 q 往上走，第一个在 Set 里的节点就是答案。也可以用两个指针轮流走两条路径，不用额外空间。

前端里哪里会遇到这个问题？

DOM 树就是一个例子。浏览器的 Range 有 commonAncestorContainer 属性，返回包含选区起点和终点的最深节点。DOM 节点有 parentNode，自己实现时可以用上一问的父指针做法。