#236. 二叉树的最近公共祖先

LeetCode 原题链接

#题目描述

给定一棵二叉树及其中两个节点 p、q，返回它们的最近公共祖先。一个节点可以是它自己的祖先。

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3

#题型判断

当前节点是否为公共祖先，取决于 p、q 在左右子树中的查找结果，所以适合后序 DFS。

也就是说，要先问左右子树：“你们那里有没有找到 p 或 q？”拿到左右子树的答案后，当前节点才能判断自己是不是最近公共祖先。

#核心思路

递归函数的含义是：在以 root 为根的子树中寻找 p 和 q。

它可能返回三类结果：

• 返回 null：这棵子树里没有找到 p 或 q。
• 返回 p 或 q：这棵子树里找到了其中一个目标节点。
• 返回某个祖先节点：这棵子树里已经同时找到了 p 和 q，最近公共祖先已经确定。

递归处理时分四种情况：

1. 当前节点为空，返回 null。
2. 当前节点就是 p 或 q，返回当前节点。
3. 左右递归结果都非空，说明两个目标分别出现在左右子树，当前节点就是最近公共祖先。
4. 只有一侧非空，说明目标节点或答案只存在于那一侧，把那一侧结果继续向上传递。

#递归过程示例

以示例中的 p = 5、q = 1 为例：

节点 5 命中 p，返回 5
节点 1 命中 q，返回 1
节点 3 的左子树返回 5，右子树返回 1
左右结果都非空，说明 5 和 1 在节点 3 汇合
所以节点 3 是最近公共祖先

为什么这里的 3 是“最近”的？

因为 p 和 q 是第一次在节点 3 这里从左右两侧汇合。再往上的节点虽然也是公共祖先，但离 p、q 更远，所以不是最近公共祖先。

#代码实现

var lowestCommonAncestor = function (root, p, q) {
  if (!root || root === p || root === q) {
    return root;
  }

  const leftResult = lowestCommonAncestor(root.left, p, q);
  const rightResult = lowestCommonAncestor(root.right, p, q);

  if (leftResult && rightResult) {
    return root;
  }

  return leftResult || rightResult;
};

#为什么返回目标节点也正确

若当前节点就是 p，直接返回 p。

这里不需要继续向下查找，是因为题目允许“一个节点是它自己的祖先”：

• 如果 q 在 p 的子树中，答案就是 p。
• 如果 q 不在 p 的子树中，上层递归会把 p 和另一侧找到的 q 汇合，再确定答案。

q 命中时同理。

#复杂度分析

• 时间复杂度：O(n)，最坏情况下需要访问每个节点一次。
• 空间复杂度：O(h)，h 为树高，主要来自递归调用栈。最坏情况下树退化成链表，空间复杂度为 O(n)；平衡二叉树中为 O(log n)。

#边界与易错点

• 题目保证 p、q 都在树中；若不保证，需额外记录找到的目标数量。
• 必须比较节点引用 root === p，不能只比较值，节点值可能重复。
• 这是普通二叉树。二叉搜索树可利用大小关系，不需要遍历所有节点。
• 不要在找到 p 或 q 后返回节点值，应返回节点本身。
• 后序 DFS 的重点是先拿到左右子树结果，再决定当前节点返回什么。