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

核心一句话：都小往左、都大往右，一分叉（一小一大或等于）当前即 LCA。

完整的 BST。每条边左小右大。下面对三组不同的 p、q，分别从根 20 出发，看每一步该往哪走。

第 1 组：要找 p = 3 和 q = 12（紫色）的最近公共祖先。先记住较小是 3、较大是 12，从根 20 开始比较。

当前节点 20（橙色）。较大的 12 都还比 20 小，说明 p、q 都在左子树里 —— 往左走，去更小的一边。

节点 20 处理完，往左走（绿色=已走过的路径）。下一个要比较的是 10，继续判断 p、q 在它的哪一边。

当前节点 10（橙色）。这次 3 ≤ 10 ≤ 12 —— p、q 在这里第一次分道（一个往左、一个往右）。所以 10 就是最近公共祖先，停。

确定了：第 1 组 p=3、q=12 的最近公共祖先是 10（绿色）。从根到这里只走了 2 步，没碰其它子树。

第 1 组小结：从根沿 20 → 10 走到分叉点，最近公共祖先 = 10（绿色）。注意全程只走了一条根到节点的路径，复杂度只跟树高有关。

第 2 组：要找 p = 22 和 q = 45（紫色）的最近公共祖先。先记住较小是 22、较大是 45，从根 20 开始比较。

当前节点 20（橙色）。较小的 22 都还比 20 大，说明 p、q 都在右子树里 —— 往右走，去更大的一边。

节点 20 处理完，往右走（绿色=已走过的路径）。下一个要比较的是 30，继续判断 p、q 在它的哪一边。

当前节点 30（橙色）。这次 22 ≤ 30 ≤ 45 —— p、q 在这里第一次分道（一个往左、一个往右）。所以 30 就是最近公共祖先，停。

确定了：第 2 组 p=22、q=45 的最近公共祖先是 30（绿色）。从根到这里只走了 2 步，没碰其它子树。

第 2 组小结：从根沿 20 → 30 走到分叉点，最近公共祖先 = 30（绿色）。注意全程只走了一条根到节点的路径，复杂度只跟树高有关。

第 3 组：要找 p = 5 和 q = 8（紫色）的最近公共祖先。先记住较小是 5、较大是 8，从根 20 开始比较。

当前节点 20（橙色）。较大的 8 都还比 20 小，说明 p、q 都在左子树里 —— 往左走，去更小的一边。

节点 20 处理完，往左走（绿色=已走过的路径）。下一个要比较的是 10，继续判断 p、q 在它的哪一边。

当前节点 10（橙色）。较大的 8 都还比 10 小，说明 p、q 都在左子树里 —— 往左走，去更小的一边。

节点 10 处理完，往左走（绿色=已走过的路径）。下一个要比较的是 5，继续判断 p、q 在它的哪一边。

当前节点 5（橙色）。这次 5 ≤ 5 ≤ 8 —— p、q 在这里第一次分道（一个往左、一个往右，或一个就是它本身）。（其中 5 正好就是目标之一）所以 5 就是最近公共祖先，停。

确定了：第 3 组 p=5、q=8 的最近公共祖先是 5（绿色）。从根到这里只走了 3 步，没碰其它子树。

第 3 组小结：从根沿 20 → 10 → 5 走到分叉点，最近公共祖先 = 5（绿色）。注意全程只走了一条根到节点的路径，复杂度只跟树高有关。

边界都能被「都大往右、都小往左、否则停」这一条规则覆盖。

两个高频追问：退化到普通二叉树的解法、以及「分叉即 LCA」的正确性。