235. 二叉搜索树的最近公共祖先（中等）

Blind 75 › 235. 二叉搜索树的最近公共祖先（中等） （第 5 章）
文章工具

题目

给定一棵二叉搜索树（BST）的根节点 root，以及树中两个互不相同的节点 p、q，请返回二者的最近公共祖先（LCA）。

“公共祖先”是指：从某个节点往下走（可以不走，也就是包含它自己），能到达 p 也能到达 q；“最近公共祖先”就是所有公共祖先里深度最大的那个。

自造示例（树形如下）：

        20
       /  
      8   30
     /     
    4  12   40
       /
      10
  • p = 4, q = 10：根 20 处二者都小于 20，先下到 8；在 8 处 4 在左、10 在右，答案就是 8。
  • p = 10, q = 30：一个在根的左子树、一个在右子树，答案就是根 20。
  • p = 8, q = 10：8 本身就是 10 的祖先，答案是 8（自己也可作祖先）。

约束：节点数 2 ~ 104；节点值范围 [-109, 109]；所有节点值互不相同；p、q 是不同节点且一定都存在于树中。

思路

一句话：从根往下走，第一次遇到“两个目标不在同一侧（或当前就是目标）”的节点，它就是最近公共祖先。

先想最直白的做法：从根分别走到 p 和 q，把两条“根到目标”的路径都记下来，再从头比较，最后一个相同的节点就是 LCA。这个方法对任意二叉树都成立，但它要存两条路径，额外空间 O(h)，而且完全没用上“这是一棵二叉搜索树”的信息。

关键观察来自 BST 的顺序结构：左子树所有节点的值 < 当前节点值 < 右子树所有节点的值（其实非严格地说：左子树的值都比当前小，右子树的值都比当前大）。于是站在任意节点上，只比较三个值，就能判断 p、q 的走向：

  • 两个都小于当前值 → 二者都在左子树里，LCA 也在左子树；
  • 两个都大于当前值 → 二者都在右子树里，LCA 也在右子树；
  • 否则 → 一个在左、一个在右，或者当前节点本身就是 p/q 之一；这时“两条路径在这里第一次分叉”，当前节点就是 LCA。

所以选定做法：不存路径、不回溯，只用一根指针从根往下走，每次按大小关系把搜索范围砍掉一半；直到不再满足“同在左”或“同在右”，直接返回当前节点。

解法

维护一个当前节点，循环判断：

  1. 若 p 和 q 的值都小于当前节点值，则移动到左孩子；
  2. 否则若两者都大于当前节点值，则移动到右孩子；
  3. 其余情况（一左一右，或命中其中一个）直接返回当前节点。

题目保证两个目标一定存在，所以循环必然在某一轮停下；末尾的兜底返回只是为了让编译器和类型检查满意。

用示例走一遍 p = 4, q = 10：

当前节点p、q 与当前值的关系判定下一步
204、10 都小于 20同在左子树 → 向左8
84 小于 8，10 大于 8分叉 → 就是 LCA返回 8

再看 p = 10, q = 30：第一轮站在 20，10 小于 20、30 大于 20，方向已经不一致，直接返回根 20。

下图把上面 3 个步骤串成流程，并逐步演示：

235. 二叉搜索树的最近公共祖先（中等） 解法步骤流程图
图① 解法步骤流程图（共 3 步）。
235. 二叉搜索树的最近公共祖先（中等） 按步骤逐步执行的动画
动图② 按步骤依次推进（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。