LeetCode 236. 二叉树的最近公共祖先

约 5 分钟
文章信息 30 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 历史考题 200-500 LeetCode 75 LeetCode 热题 100 面试经典 150 题 腾讯 字节 阿里 华为 微软 亚马逊 美团 拼多多 京东 小米 百度 网易 小红书 快手 滴滴 B站 虾皮 联想 深信服 猿辅导
标签
深度优先搜索 树 二叉树

题目描述

✅ 236. 二叉树的最近公共祖先

image-20260928184111371

image-20260928184111372

题意分析

给定一棵普通二叉树以及其中两个不同节点 p、q，返回同时包含这两个节点的最深祖先节点。节点也可以作为自己的祖先，所以当一个目标是另一个目标的祖先时，答案就是这个目标本身。

题目保证 p、q 都存在于树中，输入给出的是节点本身，代码按节点引用比较。这里不是二叉搜索树，不能根据节点值大小判断目标在左侧还是右侧，需要从子树的查找结果中判断两条路径在哪里汇合。

解法：后序递归

核心思路

[!blue]

让递归函数返回当前子树关于两个目标的查找结果：没有目标时返回空；只有一个目标时返回该目标；两个目标都在子树中时，返回它们在这棵子树内的最近公共祖先。这样父节点只需合并左右子树各一个返回值，不必保存完整路径。

空节点直接返回空。若当前节点就是 p 或 q，也可以直接返回它：如果另一个目标在它下面，它已经是最近公共祖先；如果另一个目标在别处，把当前目标上传即可，真正的公共祖先会在更上层确定。因此不需要为了区分这两种情况继续遍历这个目标的后代。

当前节点不是目标时，先递归检查左右子树。如果两边都返回非空，由于两棵子树不相交、目标只有两个，说明 p、q 分别位于两侧。当前节点同时包含两者，而它的任何一个子节点都无法同时包含两者，所以当前节点就是最近公共祖先。

如果只有一边返回非空，另一边就没有目标，不会形成新的汇合点。非空结果可能是单个目标，也可能是子树内部已经找到的最近公共祖先，直接原样上传即可。特别是已经找到的答案不会被上层覆盖：两个目标都在这一侧，另一侧必为空，上层也只会继续上传它。

如果两边都为空，就返回空。题目保证两个目标都存在，因此从整棵树的根开始调用后，最终非空返回值一定是两者的最近公共祖先，而不会只是找到一个目标却漏掉另一个。

解题步骤

  1. 当前节点为空，或恰好是 p、q 之一时，直接返回当前节点。
  2. 否则分别递归左右子树，得到 left、right 两个查找结果。
  3. 若两者都非空，返回当前节点，表示两个目标在这里汇合。
  4. 若只有一侧非空，返回这一侧；若都为空，则返回空。
  5. 以原树根节点调用递归，返回值就是答案。

代码实现

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

        return left != null ? left : 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)$，每个节点最多访问一次，最坏情况下需要检查整棵树。
  • 空间复杂度：$O(h)$，h 为树高，用于递归调用栈；平衡树为 $O(\log n)$，退化成链时为 $O(n)$。

关键点总结

[!green]

  • 返回值表示当前子树对目标节点的查找结果，合并发生在后序位置。
  • 未直接命中目标时，左右结果都非空表示两侧在当前节点汇合；当前节点本身是目标时，也可能就是最近公共祖先。
  • 比较的是节点引用，不是节点值。
  • 题目保证 p 和 q 都存在于树中，因此命中目标节点后可以直接返回。

易错点总结

[!yellow]

  • 左侧找到节点后就跳过右侧，会漏掉两个目标分处左右子树的情况。
  • 先返回任一非空子树，再判断两侧是否都非空，会错过当前汇合点。
  • 用节点值代替节点引用，在允许重复值的变体中会误判。
  • 若题目不保证两个目标都存在，不能直接沿用命中即返回的逻辑。

相似题目

题目 难度 关联与区别
235. 二叉搜索树的最近公共祖先 中等 原题是BST，可按数值范围剪枝；本题需要合并左右子树的目标信息。
1123. 最深叶节点的最近公共祖先 中等 把两个指定节点扩展成所有最深叶子，仍可后序合并深度与祖先信息。
补充题 207. 二叉树的最近公共祖先 中等 都沿树查找两个目标并确定首次汇合的祖先；补充题先按节点值定位目标。
865. 具有所有最深节点的最小子树 中等 递归向上传递目标命中信息；本题左右分别命中时确定最近公共祖先，该题定位包含所有最深节点的最小子树。
1644. 二叉树的最近公共祖先 II 中等 最近公共祖先系列。II 不保证两个目标存在，需要在后序查找时确认两个目标都已找到。
1650. 二叉树的最近公共祖先 III 中等 最近公共祖先系列。III 提供父指针，可把两条祖先链视为相交链表；本题从根向下查找。
1676. 二叉树的最近公共祖先 IV 中等 最近公共祖先系列。IV 把两个目标扩展成目标集合，后序合并时统计子树覆盖的目标数量。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/69502621
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！