给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

说明 1：所有节点的值都是唯一的。
说明 2：p、q 为不同节点且均存在于给定的二叉搜索树中。

思路

有几种情况

  1. 某个节点的左、右子树分别包含 p 和 q 时，该节点即目标节点（下文称为 typicalNode）
  2. 若 p 为 q 的子孙节点，q 即目标节点
  3. 若 q 为 p 的子孙节点，p 即目标节点

因此在递归遍历时，将符合条件的节点持续向上返回即可。

由于 说明 2（p、q 为不同节点且均存在于给定的二叉搜索树中），递归可采用前序遍历，若当前节点为 p 或者 q 时，直接返回即可（兼容情况 1 的子步骤和情况 2、3，最终都能输出正确结果）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var lowestCommonAncestor = function (node, p, q) {
  // 匹配到 p / q，直接返回
  if (!node || node === p || node === q) {
    return node
  }
  const left = lowestCommonAncestor(node.left, p, q)
  const right = lowestCommonAncestor(node.right, p, q)
  // 准确命中情况 1，typicalNode 即当前节点
  if (left && right) {
    return node
  }
  // 当 left 或 right 不为空时，其可能值为 p / q / typicalNode
  // 若为 p / q，可能是情况 1 的子步骤，在 typicalNode 命中前的递归返回，也可能是情况 2、3
  // 若为 typicalNode，则一定是情况 1，typicalNode 命中之后的递归返回
  return left || right
}