235-LowestCommonAncestorofaBinarySearchTree.md

二叉搜索树的最近公共祖先

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

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

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

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

分析：

这个问题要求我们在一个二叉搜索树（BST）中找到两个给定节点的最近公共祖先（LCA）。在 BST 中，所有左子树上的节点的值都小于它的根节点，所有右子树上的节点的值都大于它的根节点。这个性质可以用来优化寻找 LCA 的过程。

1. 遍历树：从根节点开始遍历树，对于每个节点，比较 p 和 q 的值与当前节点的值。
2. 比较值：如果 p 和 q 的值都小于当前节点的值，那么 LCA 一定在左子树中；如果都大于，那么 LCA 在右子树中。
3. 找到 LCA：如果 p 和 q 的值一个小于当前节点的值，一个大于，或者其中之一等于当前节点的值，那么当前节点就是 LCA。

思路：

1. 递归遍历：从根节点开始递归遍历树。
2. 比较节点值：对于每个节点，比较 p 和 q 的值。
   • 如果 p 和 q 的值都小于当前节点的值，那么 LCA 在左子树中。
   • 如果 p 和 q 的值都大于当前节点的值，那么 LCA 在右子树中。
   • 如果 p 和 q 的值一个小于当前节点的值，一个大于，或者其中之一等于当前节点的值，那么当前节点就是 LCA。
3. 返回 LCA：根据上述比较，返回 LCA 节点。

时间复杂度：O(h)，其中 h 是树的高度。在最坏的情况下，我们可能需要遍历整棵树的高度。 空间复杂度：O(h)，这是因为递归栈的深度最多为树的高度。在最坏的情况下，树可能是完全不平衡的，导致递归栈深度等于树的高度。

const lowestCommonAncestor = (root, p, q) => {
  if (p.val < root.val && q.val < root.val) {
    return lowestCommonAncestor(root.left, p, q);
  }
  if (p.val > root.val && q.val > root.val) {
    return lowestCommonAncestor(root.right, p, q);
  }
  return root;
};