LeetCode 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

2022-04-19 HGNULB 约 9 分钟

文章信息 8 个分类 4 个标签

分类

LeetCode CodeTop 简单未解决 2-5 字节跳动剑指 Offer 剑指 Offer（第 2 版）

题目描述

✅ 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

题意分析

在一棵二叉搜索树里给定两个节点 p、q，找出深度最大的、同时是二者祖先的节点。题目同样声明「一个节点也可以是它自己的祖先」，所以当 p 恰好位于 q 的上方时，答案就是 p 本身。

和普通二叉树版本最大的差别在于输入结构自带的那条性质：对任意节点，它左子树里的所有值都比它小，右子树里的所有值都比它大。这条全局有序性是一个极强的信号——它意味着「某个值在不在某棵子树里」这个问题可以只靠一次数值比较回答，不需要真的进去搜。

其余约束：所有节点值互不相同，p 和 q 都保证存在于树中。前者让「用值比较代替引用比较」变得安全，后者让搜索过程不必考虑找不到的情况。

边界要点清楚：p 和 q 分居根的两侧；两者都在同一侧；其中一个恰好就是当前节点（此时它就是答案）；以及题目并没有说 p.val 一定小于 q.val，所以任何写法都不能预设两者的大小顺序。

解法：利用 BST 性质

核心思路

把普通二叉树的做法直接搬过来当然可行：后序递归，看两个目标分别落在哪一侧。但那要遍历整棵树，时间是 $O(n)$，完全浪费了搜索树的有序性——就像拿到一本按字母排序的词典却从第一页开始翻。

关键观察是：设当前节点值为 $v$，那么「p 在左子树里」这件事等价于 $p.val < v$，「p 在右子树里」等价于 $p.val > v$，判断只需一次比较。于是三种情形被完全区分开来：两个目标值都小于 $v$，说明它们都在左子树，当前节点是二者的公共祖先但不是最近的，答案还在下面；都大于 $v$，同理答案在右子树；剩下的所有情况——一个小一个大，或者其中一个恰好等于 $v$——都意味着当前节点就是那个分叉点。

为什么分叉点就是最近公共祖先：如果 $p.val$ 和 $q.val$ 一个在 $v$ 左边一个在右边，那么 $p$、$q$ 分居两棵子树，再往下走任何一步都只会进入其中一侧，必然丢掉另一个目标，所以当前节点已经是能同时覆盖二者的最深节点。而如果某一个目标的值恰好等于 $v$，说明这个目标就是当前节点，按「节点可以是自己的祖先」的约定，它自己就是答案。

于是维持这条不变量：循环中的 cur 始终是「同时包含 p 和 q 的子树」的根。 初始时 cur = root，整棵树当然包含二者；每一次下移都是在确认两个目标同在某一侧之后才做的，所以移动后的子树仍然同时包含二者，不变量保持。当不变量成立且当前节点不再能往下移时，它就是答案。

因为每步只走一条路、不需要回溯，整个过程可以写成一个 while 循环，连递归栈都省了，空间降到常数。

解题步骤

令 cur 从根节点出发，进入循环。为什么不用递归：搜索路径是单向下降的，没有「先算子问题再合并」的需求，尾递归形态天然可以改写成迭代，顺便把 $O(h)$ 的栈开销降为 $O(1)$。

若 p.val < cur.val 且 q.val < cur.val，令 cur = cur.left。为什么可以整体左移：由搜索树性质，两个目标都严格小于当前值就必然都位于左子树，右子树和当前节点都不可能是答案。

否则若 p.val > cur.val 且 q.val > cur.val，令 cur = cur.right。为什么这两个条件必须都写成「与」：只要有一个目标在另一侧，就不能移动，否则会把它甩掉。

其余情况直接返回 cur。为什么剩下的都是答案：能走到这一分支，说明两个值要么分列当前值两侧，要么其中之一等于当前值，两种情形下当前节点都是深度最大的公共祖先。

循环之外的 return null 只是为了让函数签名完整。为什么实际不会执行到：题目保证两个节点都在树中，不变量说明 cur 所在子树始终包含它们，因此在走到空节点之前一定会命中返回分支。

以官方样例 root = [6,2,8,0,4,7,9,null,null,3,5]、p = 2、q = 8 走一遍：这棵树根为 6，左子树根为 2（孩子是 0 和 4，4 的孩子是 3 和 5），右子树根为 8（孩子是 7 和 9）。cur = 6：判断是否都小于 6，$2<6$ 成立但 $8<6$ 不成立，不左移；判断是否都大于 6，$2>6$ 就不成立，不右移；落入第三分支，返回节点 6。答案是 6，恰好对应两个目标分居根的左右两侧。

再看祖先关系的那组 p = 2、q = 4：cur = 6，$2<6$ 且 $4<6$，两个目标都在左子树，令 cur = 2。新的一轮：$2<2$ 不成立，不左移；$2>2$ 不成立，不右移；落入第三分支，返回节点 2。这里正是「p 等于当前节点」的情形，p 是 q 的祖先，答案就是 p 自己。把比较写成 <=、>= 就会毁掉这个分支：换成 p = 2、q = 0，cur 从 6 左移到 2 后，2 <= 2 && 0 <= 2 成立会让它继续左移到 0，再由 2 >= 0 && 0 >= 0 右移到空，循环耗尽只能返回空，而正确答案是节点 2。

代码实现

// 若 p、q 均大于当前节点，则 LCA 在右子树。
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode cur = root;
        while (cur != null) {
            if (p.val < cur.val && q.val < cur.val) {
                cur = cur.left;
            } else if (p.val > cur.val && q.val > cur.val) {
                cur = cur.right;
            } else {
                return cur;
            }
        }
        return null;
    }
}

// 若 p、q 均大于当前节点，则 LCA 在右子树。
func lowestCommonAncestor(root *TreeNode, p *TreeNode, q *TreeNode) *TreeNode {
    cur := root
    for cur != nil {
        if p.Val < cur.Val && q.Val < cur.Val {
            cur = cur.Left
        } else if p.Val > cur.Val && q.Val > cur.Val {
            cur = cur.Right
        } else {
            return cur
        }
    }
    return nil
}

复杂度分析

时间复杂度：$O(h)$，其中 $h$ 是树高。凭据：每轮循环只做两三次数值比较然后向下走一层，绝不回头，因此循环次数不超过从根到答案的路径长度；树平衡时是 $O(\log n)$，退化成链状时是 $O(n)$。

空间复杂度：$O(1)$，凭据：写成迭代后只有一个 cur 指针在移动，既没有递归栈也没有辅助容器；若改写成递归版本则会退化到 $O(h)$ 的栈开销。

关键点总结

看到「二叉搜索树」四个字，第一反应应该是「能不能只走一条路」。有序性把「某个值在不在这棵子树里」从一次遍历降成一次比较，这是所有 BST 题提速的共同来源。

判定条件要写成「两个目标同侧才移动」，也就是两个比较之间用与。只要有一个目标落在另一侧，当前节点就已经是分叉点，不能再往下走。

三个分支中，「其余情况返回当前节点」这一支把「一左一右」和「其中一个就是当前节点」两种情形合并了。能看出这两种情形的答案一致，就不用写四个分支。

单向下降的递归都可以无脑改成 while 循环。判断标准是「递归调用的结果是否被直接返回、没有任何后续合并」，本题正是如此，改完白送一个 $O(1)$ 空间。

面试视角：一定要用比较写成严格不等号。用 <=、>= 会在「一个节点是另一个的祖先」时越过正确答案继续下降，这是本题唯一的坑，也是面试官最常构造的用例。

面试视角：被追问「不用 BST 性质怎么做」时，要能立刻给出普通二叉树的后序递归版本并指出复杂度从 $O(h)$ 退化到 $O(n)$；反过来若被问「树里有重复值怎么办」，则要指出值比较不再可靠，必须回到引用比较的通用解法。

易错点总结

错误写法：把两个比较写成 <= 和 >=。用例 p = 2、q = 0，树根为 6 → 走到节点 2 时 2 <= 2 && 0 <= 2 成立继续左移到 0，再由 2 >= 0 && 0 >= 0 右移到空，最终返回空，而正确答案是节点 2。

错误写法：预设 p.val < q.val，把判定写成 if (q.val < cur.val) 左移 else if (p.val > cur.val) 右移。用例 p = 8、q = 2 → 传入顺序反过来时两个条件都不成立，立刻返回根节点；若两者本应在同一侧，答案就浅了。

错误写法：两个条件之间用「或」而不是「与」，写成 p.val < cur.val || q.val < cur.val。用例 p = 2、q = 8，根为 6 → 只要有一个目标偏小就左移，直接把节点 8 甩在右子树里，一路走到空返回空。

错误写法：只判断左移条件，把「不满足就右移」当成 else。用例 p = 2、q = 8 → 不满足左移条件后被无条件右移到节点 8，返回 8，漏掉了「当前节点即为答案」这个分支。

错误写法：直接搬普通二叉树的后序递归，不用有序性。用例任意退化成链的 BST → 答案仍然正确，但时间从 $O(h)$ 变成 $O(n)$，且在面试里等于没读懂题目给的条件。

错误写法：递归版本忘记把子调用的结果 return 出去，写成 lowestCommonAncestor(root.left, p, q); 就结束。用例任意需要下降的输入 → 函数返回默认值，答案恒为空。

错误写法：认为最近公共祖先必须严格是两者的上层节点，于是在发现 cur == p 时返回 cur 的父节点。用例 p = 2、q = 4，2 是 4 的祖先 → 返回节点 6，比正确答案 2 浅了一层。

错误写法：忘了循环退出后的返回值，或让函数在某条路径上没有返回。用例任意输入 → 在 Java 中直接编译不过；即使补上，也要理解题目保证节点存在，这条返回实际不可达。

错误写法：把节点值缓存到局部变量后又在下降过程中忘记更新，例如在循环外取 int v = cur.val。用例任意需要多次下降的输入 → 比较始终基于根节点的值，第二轮起判断全错。

错误写法：在含重复值的搜索树变体上继续用值比较。用例存在两个值都是 2 的节点 → 比较无法区分是哪一个，可能在错误的分支上提前返回；这类变体只能退回引用比较或额外记录路径。

相似题目

题目	难度	考察点
235. 二叉搜索树的最近公共祖先	中等	本题的主站原题，可直接对照迭代与递归两种写法
236. 二叉树的最近公共祖先	中等	去掉有序性后必须后序递归，复杂度升到 $O(n)$
1644. 二叉树的最近公共祖先 II	中等	节点不保证存在，需统计命中个数而非提前返回
剑指 Offer 68 - II. 二叉树的最近公共祖先	简单	普通二叉树版本，重点在递归返回值的语义定义
面试题 04.08. 首个共同祖先	中等	同类问题，可练习父指针加祖先集合的解法