Binary Search Tree Lowest Common Ancestor

题目

给定一棵二叉搜索树（BST）的根节点 root，以及树中的两个节点 a 和 b。需要找出它们的最近公共祖先（Lowest Common Ancestor, LCA）。

定义： LCA 是树中最深的、同时拥有 a 和 b 作为子孙的节点。一个节点也可以是它自己的祖先，因此如果 a 本身就在 b 的路径上（或反之），LCA 就是那个更上层的节点。

由于给定的是 BST，节点值满足：

左子树所有值 < 当前节点值
右子树所有值 > 当前节点值

这让 LCA 的查找可以非常高效。

利用 BST 性质求 LCA（核心思想）

设：

a.val
b.val
当前节点 node.val

利用 BST 的有序性可以得到：

如果 a.val 和 b.val 都小于 node.val LCA 必在 node.left 子树中
如果 a.val 和 b.val 都大于 node.val LCA 必在 node.right 子树中
否则当前节点 node 就是 LCA（因为一左一右，或被夹在中间，或 node 本身等于其中一个节点）

为什么？

因为 BST 的值严格排列，若分布到左右不同方向，说明当前节点就是它们第一次路径分叉的位置，也就是 LCA。

代码

迭代法

function lowestCommonAncestor(root: TreeNode, a: TreeNode, b: TreeNode): TreeNode {
  let node = root;
  const v1 = a.val;
  const v2 = b.val;

  while (node !== null) {
    if (v1 < node.val && v2 < node.val) {
      node = node.left;
    } else if (v1 > node.val && v2 > node.val) {
      node = node.right;
    } else {
      return node;
    }
  }

  throw new Error("Invalid input"); // a 和 b 保证存在，逻辑上不会到这里
}

递归法

function lowestCommonAncestor(root: TreeNode, a: TreeNode, b: TreeNode): TreeNode {
  if (root === null) return null;

  const v1 = a.val;
  const v2 = b.val;

  if (v1 < root.val && v2 < root.val) {
    // 都在左子树
    return lowestCommonAncestor(root.left, a, b);
  }

  if (v1 > root.val && v2 > root.val) {
    // 都在右子树
    return lowestCommonAncestor(root.right, a, b);
  }

  // 否则当前节点就是分叉点（或等于其中一个节点），即 LCA
  return root;
}

Binary Search Tree Lowest Common Ancestor

题目

利用 BST 性质求 LCA（核心思想）

代码

迭代法

递归法

目录