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

题目 / Problem

中文： 给定一棵二叉搜索树（BST），请找出树中两个指定节点 p 和 q 的最近公共祖先（LCA）。

最近公共祖先是同时拥有 p 和 q 作为后代的最深节点，其中允许一个节点成为它自己的后代。换句话说，如果 p 是 q 的祖先，那么 p 也可以是它们的最近公共祖先。
The lowest common ancestor is the deepest node that has both p and q as descendants, and a node is allowed to be a descendant of itself.

English: Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

示例 / Examples

以下三个示例使用的二叉搜索树结构：
The following binary search tree is used in the examples:

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

Example 1

二叉搜索树：节点 2 和 8 的最近公共祖先 / BST: LCA of nodes 2 and 8

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

解释 / Explanation:
节点 2 和节点 8 分别位于节点 6 的两侧，因此最近公共祖先是 6。
Nodes 2 and 8 lie on opposite sides of node 6, so their LCA is 6.

Example 2

二叉搜索树：节点 2 和 4 的最近公共祖先 / BST: LCA of nodes 2 and 4

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

解释 / Explanation:
节点 2 是节点 4 的祖先。由于节点可以是自己的后代，因此最近公共祖先是 2。
Node 2 is an ancestor of node 4. Because a node can be a descendant of itself, their LCA is 2.

Example 3

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

约束 / Constraints

树中的节点数在 [2, 10⁵] 范围内。
The number of nodes in the tree is in the range [2, 10⁵].
-10⁹ <= Node.val <= 10⁹
所有节点的值互不相同。
All Node.val values are unique.
p != q
p 和 q 一定存在于这棵二叉搜索树中。
Both p and q exist in the BST.

解题思路：利用 BST 的有序性质 / Approach: Use the BST Ordering Property

二叉搜索树中的每个节点都满足：
Every node in a binary search tree satisfies:

左子树中的所有值都小于当前节点的值。
Every value in the left subtree is smaller than the current node's value.
右子树中的所有值都大于当前节点的值。
Every value in the right subtree is greater than the current node's value.

从根节点开始，设当前节点为 current：
Starting at the root, let the current node be current:

如果 p.val 和 q.val 都小于 current.val，说明两个节点都在左子树中，继续向左搜索。
If both p.val and q.val are smaller than current.val, both nodes are in the left subtree, so continue left.
如果 p.val 和 q.val 都大于 current.val，说明两个节点都在右子树中，继续向右搜索。
If both values are greater than current.val, both nodes are in the right subtree, so continue right.
否则，两个节点位于当前节点的两侧，或者当前节点就是 p 或 q。此时 current 就是最近公共祖先。
Otherwise, the nodes lie on opposite sides, or current is itself p or q. In either case, current is the LCA.

这个“分叉点”是从根节点向下搜索时遇到的第一个同时覆盖 p 和 q 的节点，因此它就是最深的公共祖先。
This split point is the first node encountered from the root that contains both p and q in its subtree, so it is their lowest common ancestor.

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) {
  let current = root;

  while (current !== null) {
    if (p.val < current.val && q.val < current.val) {
      current = current.left;
    } else if (p.val > current.val && q.val > current.val) {
      current = current.right;
    } else {
      return current;
    }
  }

  return null;
}

题目保证 p 和 q 都存在于树中，因此按照约束一定会在循环中找到最近公共祖先。末尾的 return null 只是函数的兜底返回值。
The problem guarantees that both nodes exist in the tree, so the LCA will be found inside the loop. The final return null is only a fallback.

执行过程 / Walkthrough

Example 1：`p = 2`，`q = 8`

当前节点 / `current`	比较 / Comparison	操作 / Action
`6`	`2 < 6 < 8`	两个节点在两侧，返回 `6` / Nodes split; return `6`

Example 2：`p = 2`，`q = 4`

当前节点 / `current`	比较 / Comparison	操作 / Action
`6`	`2 < 6` 且 `4 < 6`	两者都在左侧，移动到 `2` / Both are left; move to `2`
`2`	`current === p`	当前节点就是公共祖先，返回 `2` / Current node is the LCA; return `2`

当 current 等于 p 时，两个值不可能同时严格小于或严格大于 current.val，所以会进入 else 并正确返回 p。
When current equals p, both values cannot be strictly smaller or strictly greater than current.val, so execution reaches else and correctly returns p.

复杂度 / Complexity

设二叉搜索树的高度为 h。
Let the height of the binary search tree be h.

时间复杂度：O(h)，每次只沿树的一条路径向下移动。
Time: O(h), because the algorithm follows only one path down the tree.
- 平衡二叉搜索树中为 O(log n)。
  It is O(log n) in a balanced BST.
- 树退化为链表时，最坏为 O(n)。
  It is O(n) in the worst case when the tree is skewed.
空间复杂度：O(1)，迭代解法只使用一个额外指针。
Space: O(1), because the iterative solution uses only one extra pointer.

递归解法 / Recursive Approach

同样的判断逻辑也可以递归实现：
The same decision process can be implemented recursively:

function lowestCommonAncestorRecursive(root, p, q) {
  if (p.val < root.val && q.val < root.val) {
    return lowestCommonAncestorRecursive(root.left, p, q);
  }

  if (p.val > root.val && q.val > root.val) {
    return lowestCommonAncestorRecursive(root.right, p, q);
  }

  return root;
}

时间复杂度 / Time: O(h)
空间复杂度 / Space: O(h)，递归调用栈的深度取决于树高。
The recursion stack depth depends on the height of the tree.

由于节点数最多达到 10⁵，极度倾斜的树可能使递归调用栈过深，因此迭代解法更加稳妥。
Because the tree may contain up to 10⁵ nodes, a highly skewed tree can make the recursion stack too deep, so the iterative solution is safer.

与普通二叉树解法的区别 / Difference from a General Binary Tree

普通二叉树没有“左小右大”的性质，通常需要分别搜索左右子树，时间复杂度为 O(n)。
A general binary tree lacks the ordered left-smaller/right-greater property, so both subtrees usually need to be searched, resulting in O(n) time.

本题是二叉搜索树，可以根据节点值直接排除一整棵子树，将搜索限制在一条路径上。
Because this problem uses a BST, node values let us eliminate an entire subtree and restrict the search to a single path.

易错点 / Common Pitfalls

不要忽略二叉搜索树的有序性质，否则会写成普通二叉树的 O(n) 解法。
Use the BST ordering property instead of defaulting to the general O(n) binary-tree solution.
最近公共祖先可以是 p 或 q 本身。
The LCA may be p or q itself.
只有当两个节点都严格小于或都严格大于当前节点时，才能继续向同一侧移动。
Move to one side only when both nodes are strictly smaller or both are strictly greater than the current node.
返回的是节点对象，不是节点的值。
Return the node object, not its value.
不需要假设 p.val < q.val；当前判断对两种顺序都适用。
Do not assume p.val < q.val; the comparisons work in either order.

Lowest Common Ancestor of a Binary Search Tree