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

约 4 分钟
文章信息 8 个分类 4 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 剑指 Offer 剑指 Offer（第 2 版） 字节
标签
深度优先搜索 树 二叉树 二叉搜索树

题目描述

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

image-20260928220457933

image-20260928220457934

题意分析

在节点值互不相同的二叉搜索树中，找到同时包含 p、q 且深度最大的祖先节点。题目保证两个目标都存在，并允许节点是自己的祖先，所以答案也可能就是 p 或 q。

解法：利用 BST 性质

核心思路

[!blue]

二叉搜索树的左子树中所有值都小于根，右子树中所有值都大于根，因此比较两个目标与当前节点的值，就能判断它们是否仍在同一侧，无需搜索两条分支。

从根开始，始终保持“当前子树包含两个目标”。若 p、q 的值都小于当前值，两个目标都在左子树，左子树内部已经存在公共祖先，答案不必停留在当前节点，继续向左找更深的位置。都大于当前值时同理向右。这样的移动保留两个目标，也保留它们的最近公共祖先。

当两个目标分居两侧时，任何更深的节点都只属于其中一侧，不可能再同时成为两者祖先，因此当前节点就是最近公共祖先。另一种停止情况是当前值等于某个目标：当前子树仍包含另一目标，所以当前节点就是它的祖先，而当前节点的后代不可能成为当前节点自己的祖先，答案同样已经确定。

因而沿一条路径不断下降，第一次不能继续向同一侧移动的位置就是答案。每次下降一层，最多经过树高个节点；在两个目标都存在的保证下，会在走到空节点之前找到答案。

解题步骤

  1. 令 cur 指向根节点。
  2. 若两个目标值都小于 cur.val，令 cur = cur.left。
  3. 若两个目标值都大于 cur.val，令 cur = cur.right。
  4. 否则返回 cur，它是分叉点或其中一个目标本身。两个目标不需要预先按值排序。

代码实现

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 *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)$，迭代只保存当前节点。

关键点总结

[!green]

  • 每次移动后，当前子树仍同时包含两个目标。
  • 同侧就能继续找更深的公共祖先，分叉或命中目标时停止。
  • 严格不等号保留了“目标本身也是祖先”的情况。

易错点总结

[!yellow]

  • 同侧判断必须用“且”；只要一个目标更小就向左，会丢掉另一侧的目标。
  • 使用小于等于或大于等于继续下降，会越过答案恰好是目标的情况。
  • 不能假定 p.val < q.val，代码对两个目标采用对称判断。
  • 此方法依赖搜索树的有序性，不能直接用于普通二叉树。

相似题目

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