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

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

题目描述

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

image-20260928184111371

image-20260928184111372

题意分析

在普通二叉树中找 p、q 的最近公共祖先，返回原树中的节点。题目保证两个不同目标都存在，节点也可以是自己的祖先；树没有按值排序，必须根据实际子树关系判断。

解法：递归后序遍历

核心思路

[!blue]

递归不仅返回最终答案，也要让父节点知道目标出现在哪一侧。约定：子树不含目标时返回空；只含一个目标时返回该目标；同时含两个目标时返回它们在这棵子树中的最近公共祖先。一个节点返回值就足以表达后续合并所需的信息。

空节点没有目标，直接返回空。遇到 p 或 q 时也直接返回当前节点：如果另一个目标就在它下面，当前节点已是最近公共祖先；如果另一个目标在子树外，当前节点作为已找到的目标继续向上参与合并。因此这里不必先搜索它的后代。

对其余节点，先递归取得左右子树的结果，再合并。如果左右都非空，两侧各包含一个目标，任何更深的节点只能属于一侧，当前节点就是最近公共祖先。如果只有一侧非空，则把那侧结果原样上传：它可能是一个尚未汇合的目标，也可能已经是两者更深的最近公共祖先，不能用当前节点替换它。两侧都为空就返回空。

两个目标都存在，所以最终要么在某个节点的左右两侧汇合，要么一个目标就是另一个的祖先。这两种情况都被上述返回规则覆盖，向上保留更深答案就能得到最近公共祖先。

解题步骤

  1. 若当前节点为空，或与 p、q 中某个节点相同，直接返回当前节点。
  2. 分别递归左右子树，取得 left、right。
  3. 若两者都非空，返回当前节点。
  4. 否则返回唯一的非空结果；若两者都为空，也返回空。

代码实现

class Solution {
    // 返回子树中的目标信息：无目标为空，仅一个上传目标，两个则上传最近公共祖先。
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 命中目标直接上传，它可能就是另一个目标的祖先。
        if (root == null || root == p || root == q) {
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 两侧分别含有目标，当前根是它们的汇合点。
        if (left != null && right != null) {
            return root;
        }

        if (left != null) {
            return left;
        }

        // 左侧为空时上传右侧，右侧也为空则自然返回空。
        return right;
    }
}

// 返回子树中的目标信息：无目标为空，仅一个上传目标，两个则上传最近公共祖先。
func lowestCommonAncestor(root *TreeNode, p *TreeNode, q *TreeNode) *TreeNode {
    // 命中目标直接上传，它可能就是另一个目标的祖先。
    if root == nil || root == p || root == q {
        return root
    }

    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)

    // 两侧分别含有目标，当前根是它们的汇合点。
    if left != nil && right != nil {
        return root
    }
    if left != nil {
        return left
    }
    // 左侧为空时上传右侧，右侧也为空则自然返回空。
    return right
}

复杂度分析

  • 时间复杂度：$O(n)$，其中 n 为节点数。每个被访问的节点最多处理一次，遇到目标后可能提前结束该子树搜索。
  • 空间复杂度：$O(h)$，其中 h 为树高，用于递归栈；退化成链时可达 $O(n)$。

关键点总结

[!green]

  • 递归结果既可能是一个目标，也可能是已经找到的最近公共祖先。
  • 两侧都有结果才在当前节点汇合，一侧有结果则继续上传原节点。
  • 目标均存在的题目保证，使最终返回的节点一定是两者祖先。

易错点总结

[!yellow]

  • 左侧非空就立即返回，会漏掉右侧可能存在的另一个目标，必须先取得两侧结果。
  • 一侧非空时返回当前根，会把已经找到的更深答案替换成较远祖先。
  • 一侧非空时返回空，会丢掉父节点还需要的目标信息。
  • 普通二叉树不能按值大小决定搜索方向；代码通过节点身份判断是否命中目标。

相似题目

题目 难度 关联与区别
235. 二叉搜索树的最近公共祖先 中等 原题是BST，可按数值范围剪枝；本题需要合并左右子树的目标信息。
1123. 最深叶节点的最近公共祖先 中等 把两个指定节点扩展成所有最深叶子，仍可后序合并深度与祖先信息。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/24707848
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！