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

约 5 分钟
文章信息 13 个分类 7 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 字节跳动 阿里巴巴 快手 腾讯 猿辅导 滴滴 京东 拼多多
标签
深度优先搜索 树 二叉树 二叉搜索树 Binary Lifting 最近公共祖先 二叉树公共祖先问题
目录

题目描述

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

image-20241020142157385

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

题意分析

输入是一棵二叉搜索树的根，以及树中两个确实存在的节点 p 和 q，要输出「深度最大的那个同时包含 p 和 q 的子树的根」。题面还额外声明：一个节点也可以是它自己的祖先，也就是说当 p 是 q 的祖先时，答案就是 p 本身，这一条不能漏。

约束里最关键的信号是「二叉搜索树」和「所有节点值互不相同」。互不相同意味着值可以当身份用，比较 p.val 与某个节点的值就等价于比较节点本身；而搜索树性质意味着左子树全部小于根、右子树全部大于根，于是「p 在哪一侧」这个问题不用搜索就能直接判定。

这正是本题比 236 简单得多的原因。236 面对的是普通二叉树，节点值毫无规律，想知道 p 藏在左子树还是右子树，只能真的把两棵子树都递归走一遍，代价是 $O(n)$ 且必须借助递归栈回传信息。而 235 里一次值比较就替代了整趟搜索，路径是唯一确定的，走一条从根往下的链就够了，时间降到树高级别，空间还能压到常数。

边界上要考虑：p 和 q 谁大谁小题目不保证，代码不能假设 p.val <= q.val；树可能退化成一条链，此时树高等于节点数；p 或 q 可能就是根节点。

解法：利用 BST 性质迭代下探

核心思路

二叉搜索树满足：当前节点 cur 的左子树值都更小，右子树值都更大。因此只需比较 p.val、q.val 与 cur.val：两者都小则最近公共祖先一定在左子树；两者都大则一定在右子树；否则两条搜索路径在当前节点第一次分叉，cur 就是答案。

「否则」还包括 cur 恰好等于 p 或 q。节点可以是自己的祖先，而另一个目标位于其子树中，所以此时同样应返回 cur，不需要单独特判。

循环不变量：每轮开始时，cur 的子树同时包含 p 和 q。只有确认二者位于同一侧时才向该侧下移，因此不会丢失答案；第一次不能继续同向下移的位置，就是两条路径的最低分叉点。该过程只沿一条根到叶路径前进，不需要遍历整棵树。

解题步骤

  1. 从根节点开始，令游标 cur = root。
  2. 若 p、q 的值都小于 cur.val，令 cur = cur.left。
  3. 若二者的值都大于 cur.val，令 cur = cur.right。
  4. 其余情况说明二者分居两侧，或 cur 命中其中一个目标，直接返回 cur。

例如树 [6,2,8,0,4,7,9,null,null,3,5]：查询 2 和 8 时，它们在根 6 两侧，答案为 6；查询 2 和 4 时，先从 6 向左走到 2，此时命中目标节点，答案为 2。

代码实现

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;
    }
}

func lowestCommonAncestor(root, p, 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)$，迭代过程只使用一个游标。

关键点总结

  • BST 的有序性把全树搜索缩减为单路径下探。
  • 两个目标同侧才继续下移；异侧或命中目标时，当前节点就是最近公共祖先。
  • 判断应同时比较 p 和 q，不能预设二者的大小顺序。
  • 普通二叉树没有值域划分，只能用后序遍历判断左右子树是否分别命中目标，时间会变为 $O(n)$。

易错点总结

  • 用逻辑或判断「同侧」会把一左一右误判为可继续下移；必须是两个条件同时成立。
  • 不要假设 p.val < q.val，测试参数可能以任意顺序传入。
  • 分叉时应返回当前游标 cur，不是最初的 root。
  • cur 等于 p 或 q 时必须立即返回；目标节点本身可以是最近公共祖先。
  • 左右方向容易写反：两值都小向左，两值都大向右。

相似题目

题目 难度 考察点
236. 二叉树的最近公共祖先 中等 无序二叉树的后序递归 LCA
1644. 二叉树的最近公共祖先 II 中等 目标节点可能不存在的判定
1650. 二叉树的最近公共祖先 III 中等 带父指针时转化为链表相交
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 简单 同款 BST 值域下探
剑指 Offer 68 - II. 二叉树的最近公共祖先 简单 后序回传子树命中信息
面试题 04.08. 首个共同祖先 中等 同一模板的换皮考法