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

约 4 分钟
文章信息 13 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 腾讯 字节 阿里 拼多多 京东 快手 滴滴 猿辅导
标签
深度优先搜索 树 二叉树 二叉搜索树

题目描述

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

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

image-20260928220457933

image-20260928220457934

题意分析

给定一棵二叉搜索树和其中两个不同节点 p、q，返回它们的最近公共祖先。公共祖先的子树中同时包含这两个节点，“最近”指所有公共祖先中深度最大的那个；一个节点也可以作为它自己的祖先。

题目保证所有节点值唯一，并且 p、q 都存在于树中。因此可以根据目标值与当前节点值的大小，判断目标位于左侧还是右侧。返回的是树中原有的节点引用，不是单独的节点值，也不是新建的同值节点。

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

核心思路

[!blue]

从根节点开始，始终保持当前节点 cur 的子树包含两个目标。根显然满足这个条件；之后只在能够确定两个目标同处某一侧时，才一起向这一侧下降。

若 p.val 和 q.val 都小于 cur.val，由搜索树性质，它们都在左子树中。左孩子就是比当前节点更深的公共祖先候选，答案不必停在当前节点，可以令 cur = cur.left。两个值都更大时，对称地进入右子树。

如果两个目标分别位于当前节点两侧，那么它们从当前节点开始走向不同分支。任何更深节点只属于某一侧，不可能同时包含两个目标，因此当前节点就是最近公共祖先。

若 cur 本身等于某个目标，另一个目标又在当前子树中，当前节点同样是公共祖先；其严格后代不可能再成为当前节点自己的祖先，所以也不能继续下降。代码用严格的小于和大于处理同侧情况，其余情况就同时覆盖了分叉与命中目标两种终止条件。

整个过程是在追踪两条搜索路径的公共部分，只走一条向下路径，无需分别保存祖先列表或遍历无关子树。两个目标的参数顺序不影响判断，也不需要预设谁的值更小。

解题步骤

  1. 令游标 cur = root，当前子树包含两个目标。
  2. 若两个目标值都小于当前值，进入左孩子。
  3. 若两个目标值都大于当前值，进入右孩子。
  4. 否则，当前节点是两条搜索路径的分叉点或其中一个目标，直接返回它。

代码实现

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)$，只使用当前节点游标，没有递归栈或祖先列表。

关键点总结

[!green]

  • 当前子树始终同时包含两个目标，同侧时才有更深的公共祖先可继续查找。
  • 分处两侧或命中其中一个目标时，已经无法让两个目标同时落入更低的同一子树。
  • 搜索树的唯一值与有序性，让数值比较能够代表节点所在方向。

易错点总结

[!yellow]

  • 用逻辑或判断同侧，只要一个目标满足就下降，会把另一个目标丢在搜索范围外；两个条件必须同时成立。
  • 假定 p.val < q.val，会使交换参数顺序后判断错误；应对两个值对称处理。
  • 命中一个目标后还继续向下，会错过目标节点本身就是最近公共祖先的情况。
  • 找到分叉时返回最初的 root，而非当前的 cur，会把更高的公共祖先当成最近的那个。
  • 将这套按值下探的规则直接用于普通二叉树，无法保证目标所在方向；本题依赖搜索树性质。

相似题目

题目 难度 关联与区别
236. 二叉树的最近公共祖先 中等 普通树不能按值判断两个目标在哪一侧，本题可利用BST性质沿单一路径下降。
700. 二叉搜索树中的搜索 简单 同样根据目标与当前值的关系选择子树，本题在两个目标分居两侧时停止。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/80298432
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！