Lowest Common Ancestor of a Binary Tree（二叉树的最近公共祖先）

题目 / Problem

中文： 给定一棵二叉树，找到树中两个指定节点 p 和 q 的最近公共祖先（Lowest Common Ancestor，LCA）。

最近公共祖先是树中同时拥有 p 和 q 作为后代的最深节点。一个节点也可以是它自己的后代。

English: Given a binary tree, find the lowest common ancestor (LCA) of two given nodes p and q.

The LCA is the lowest node in the tree that has both p and q as descendants. A node is allowed to be a descendant of itself.

示例 / Examples

Example 1

Input:  root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3

节点 5 位于根节点 3 的左子树，节点 1 位于右子树，因此最近公共祖先是 3。
Node 5 is in the left subtree of 3, while node 1 is in its right subtree, so their LCA is 3.

Example 2

Input:  root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5

节点可以是自己的后代。由于节点 4 位于节点 5 的子树中，所以最近公共祖先是 5。
A node may be a descendant of itself. Since node 4 belongs to node 5's subtree, the LCA is 5.

Example 3

Input:  root = [1,2], p = 1, q = 2
Output: 1

约束 / Constraints

• 节点数量在 [2, 10^5] 范围内。
  The number of nodes is in the range [2, 10^5].
• -10^9 <= Node.val <= 10^9
• 所有 Node.val 互不相同。
  All Node.val values are unique.
• p !== q
• p 和 q 一定存在于树中。
  Both p and q exist in the tree.

解题思路：后序遍历 / Approach: Postorder DFS

对每个节点递归搜索其左右子树。递归函数返回的不是布尔值，而是一个有意义的节点：
Recursively search both subtrees of every node. The recursive function returns a meaningful node rather than a Boolean:

• 返回 null：当前子树中没有找到 p 或 q。
  Return null: neither p nor q was found in this subtree.
• 返回 p 或 q：当前子树中找到了其中一个目标节点。
  Return p or q: one target node was found in this subtree.
• 返回某个祖先节点：当前子树中已经找到了 p 和 q 的最近公共祖先。
  Return an ancestor node: the LCA has already been found in this subtree.

后序遍历先获得左右子树的搜索结果，再决定当前节点应该返回什么。
Postorder traversal obtains the results of the left and right subtrees before deciding what the current node should return.

核心判断 / Core Logic

对于当前节点 root：
For the current node root:

1. 如果 root 为 null，返回 null。
   If root is null, return null.
2. 如果 root === p 或 root === q，直接返回 root。
   If root === p or root === q, return root immediately.
3. 分别递归搜索左右子树，得到 left 和 right。
   Search the left and right subtrees recursively to obtain left and right.
4. 如果 left 和 right 都不为空，说明两个目标分别位于两侧，当前节点就是 LCA。
   If both are non-null, the targets lie on different sides, so the current node is the LCA.
5. 如果只有一侧不为空，返回非空的那一侧。
   If only one side is non-null, return that side.

left !== null && right !== null  → 返回当前节点 / Return current node
只有 left 非空 / Only left       → 返回 left / Return left
只有 right 非空 / Only right     → 返回 right / Return right
两侧都为空 / Both null           → 返回 null / Return null

JavaScript 实现 / JavaScript Implementation

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *   this.val = val;
 *   this.left = this.right = null;
 * }
 */

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
function lowestCommonAncestor(root, p, q) {
  if (root === null || root === p || root === q) {
    return root;
  }

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

  if (left !== null && right !== null) {
    return root;
  }

  return left !== null ? left : right;
}

执行过程 / Walkthrough

对于 Example 1，目标节点是 5 和 1：
For Example 1, the targets are 5 and 1:

          3
        /   \
       5     1
      / \   / \
     6   2 0   8
        / \
       7   4

• 在节点 3 的左子树中找到节点 5，左侧递归返回 5。
  The left subtree of 3 finds node 5 and returns 5.
• 在节点 3 的右子树中找到节点 1，右侧递归返回 1。
  The right subtree of 3 finds node 1 and returns 1.
• left 和 right 都不为空，因此节点 3 是最近公共祖先。
  Both results are non-null, so node 3 is the LCA.

对于 Example 2，搜索到节点 5 时直接返回 5。由于节点可以是自己的后代，不需要继续向下寻找节点 4 才能确认答案。
For Example 2, node 5 is returned as soon as it is reached. Because a node may be its own descendant, there is no need to continue searching for node 4 before confirming the result.

与 BST 版本的区别 / Difference from the BST Version

本题只说明它是一棵普通二叉树，没有二叉搜索树的大小关系，因此不能根据节点值决定向左还是向右搜索。
This is an ordinary binary tree with no BST ordering, so node values cannot tell us whether to search left or right.

复杂度 / Complexity

设树中有 n 个节点，树高为 h。
Let the tree contain n nodes and have height h.

• 时间复杂度 / Time: O(n)，最坏情况下需要访问整棵树。
  In the worst case, every node is visited.
• 空间复杂度 / Space: O(h)，用于递归调用栈。
  The recursive call stack uses O(h) space.
• 平衡树中 h = O(log n)；退化成链表时 h = O(n)。
  For a balanced tree, h = O(log n); for a skewed tree, h = O(n).

易错点 / Common Pitfalls

• 应比较节点引用 root === p，而不是只比较节点值。
  Compare node references with root === p, not only their values.
• 节点本身可以作为自己的后代，因此遇到 p 或 q 时可以直接返回。
  A node can be its own descendant, so return immediately upon reaching p or q.
• 这不是二叉搜索树问题，不能利用节点值的大小关系选择搜索方向。
  This is not a BST problem, so value ordering cannot determine the search direction.
• 左右递归结果都不为空时，应返回当前节点，而不是其中一个子节点。
  When both recursive results are non-null, return the current node rather than either child result.
• 当树高度可能达到 10^5 时，JavaScript 的递归实现可能超过调用栈限制；工程环境中可改用父指针映射与迭代遍历。
  With a tree height up to 10^5, JavaScript recursion may exceed the call-stack limit; an iterative traversal with a parent map can be used in production environments.