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

约 4 分钟
文章信息 27 个分类 8 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 历史考题 200-500 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 华为 拼多多 网易 小米 亚马逊 虾皮 哔哩哔哩 小红书 LeetCode 75 LeetCode 热题 100 面试经典 150 题
标签
深度优先搜索 树 二叉树 层序遍历 二叉树经典题 Binary Lifting 最近公共祖先 二叉树公共祖先问题
目录

题目描述

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

image-20230306222207038

image-20230306222212398

题意分析

输入一棵普通二叉树的根，以及树中的两个节点 p 和 q，要求返回它们深度最大的那个共同祖先节点本身，而不是它的值。

题面里有三条容易被忽略的措辞。第一，它明确规定「一个节点也可以是它自己的祖先」，所以当 p 恰好在 q 的上方时，答案就是 p，这不是特例而是正常输出之一。第二，它保证 p 和 q 都存在于树中，这条前提允许算法一旦命中就不再往下确认另一个目标是否存在——去掉这条前提，题就变成第 1644 题，写法必须改。第三，返回类型是节点指针而不是整数，说明这是「定位」而非「计算」，一路上不需要累积任何数值。

这棵树是普通二叉树，不是搜索树：节点值和位置之间没有任何关系，所以无法通过比较取值来决定往哪边走，只能对两棵子树都做搜索。同时二叉树的节点默认没有父指针，「往上找祖先」这个方向不是天然可行的——结构里只有自上而下的通路，任何做法都得先回答「向上的信息从哪来」这个问题。

需要单独想清楚的边界有三种：p 是 q 的祖先（或反之），答案是那个祖先自己；p 或 q 就是根，答案必然是根；两个节点分列根的左右子树，答案是根。而如果树只有一个节点，那 p 和 q 只能都是它，答案还是它。

解法：后序递归

核心思路

递归函数返回当前子树中找到的 p、q 或它们的最近公共祖先。当前节点为空或等于目标节点时直接返回；左右子树都返回非空时，当前节点就是首次汇合点，否则继续向上传递非空结果。

解题步骤

  • 当前节点为空、等于 p 或等于 q 时，直接返回当前节点。
  • 分别递归左右子树，得到两侧的查找结果。
  • 两侧都非空，说明 p 和 q 分处两侧，返回当前节点。
  • 只有一侧非空时返回该侧；两侧都为空时自然返回空。

代码实现

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 为树高，对应递归栈深度。

关键点总结

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

易错点总结

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

相似题目

题目 难度 考察点
235. 二叉搜索树的最近公共祖先 中等 有序性让节点值能指路，可以单路下降，不必对两棵子树都递归
1123. 最深叶节点的最近公共祖先 中等 目标不是给定的两个节点而是全部最深叶子，返回值要同时携带深度和候选答案
1644. 二叉树的最近公共祖先 II 中等 去掉「两节点必在树中」的前提，不能命中即返回，必须统计一共找到了几个
1650. 二叉树的最近公共祖先 III 中等 节点自带父指针，无需建表，问题直接退化成两条向上链求首个交点
1676. 二叉树的最近公共祖先 IV 中等 目标从两个节点推广为一个节点数组，命中判断换成集合成员测试，汇合逻辑不变
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 简单 与 235 同题换皮，用来单练搜索树上的单路下降写法
剑指 Offer 68 - II. 二叉树的最近公共祖先 简单 与本题同题换皮，可原样套用后序返回命中节点的模板
面试题 04.08. 首个共同祖先 中等 与本题同题换皮，但描述里不保证两节点一定存在，实现时要留意是否需要额外校验