最近公共祖先

最近公共祖先的定义是什么？

• 定义: 在同时包含 p、q 的所有节点中, 深度最大的那个节点;
• 位置关系: p、q 分别位于答案节点的左右子树; 或者答案节点本身就是 p 或 q, 另一个在它的子树里;

后序递归如何求最近公共祖先？

• 递归返回值: 当前子树中命中的 p、q, 或它们的最近公共祖先;
• 终止: 空节点返回 null; 命中 p 或 q 直接返回当前节点;
• 合并: 左右返回值都非空说明 p、q 分居两侧, 当前节点就是答案; 只有一侧非空就向上传递该侧结果;

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

  return dfs(root);
};

复杂度与适用条件是什么？

• 复杂度: 时间 O(n), 空间 O(n) 递归栈;
• 前提: 这是普通二叉树的解法, 默认 p、q 一定在树中;
• 二叉搜索树: 可以利用大小关系一次下降定位, 不需要后序递归;