LeetCode 1123. 最深叶节点的最近公共祖先

2026-03-31 HGNULB 约 9 分钟

文章信息 7 个分类 8 个标签

分类

题目描述

✅ 1123. 最深叶节点的最近公共祖先

题意分析

题目要的是一个节点：它是所有「深度等于全树最大深度」的叶子的公共祖先中，位置最低的那一个。注意这里的目标集合不是题目给你的两个指定节点，而是要先自己找出来的一批节点，所以这道题真正的难点在于「谁是最深叶」和「谁是它们的祖先」这两件事必须在同一次遍历里同时确定。

约束里节点数只有 1 到 1000，且每个节点的值互不相同，这两条都在说明：不需要任何按值查找的哈希索引，也不需要担心重复值造成的歧义，一次自底向上的遍历就足以承载全部信息。数据量小意味着即使写成「先求最大深度再求祖先」的两趟解法也能过，但面试官期待的是一趟就把答案带上来。

边界要单独想清楚三种：整棵树只有一个节点时，它自己既是最深叶也是答案；某个节点只有一侧子树时，最深叶只能在那一侧，答案必须从那一侧透传上来；空树按题意不会出现，但递归内部一定会走到空指针，需要一个不破坏语义的返回值。

解法：后序遍历返回深度和候选节点

核心思路

最朴素的做法是两趟：第一趟算出全树最大深度 maxDepth，第二趟再从根往下走，看左右子树是否都含有深度为 maxDepth 的叶子，都含有就停在当前节点。这个做法能对，但每次判断「某子树里最深叶的深度」都要重新递归一遍，退化成对每个节点做一次子树遍历，瓶颈就在这些被反复重算的子树高度上。

观察到的关键点是：这些重复计算完全可以合并进同一次后序遍历。一个节点在算完自己的左右子树之后，其实已经同时知道了两件事——左右子树各自的高度，以及左右子树各自内部的答案。而当前子树的答案只由这两个高度的大小关系决定，不需要再看任何别的信息。

于是把递归的返回值定义成一个二元组，这就是本题的状态定义：dfs(node) 返回 (ansNode, depth)，其中 depth 是以 node 为根的子树的高度（空子树为 0），ansNode 是「以 node 为根的子树内部，所有最深叶节点的最近公共祖先」。这个定义对任意子树都成立，是全程要维持的不变量。

在这个定义下转移是显然的：若左右高度相等，说明这棵子树的最深叶同时分布在两侧，能同时覆盖两侧的最低节点就是 node 自己；若某一侧更高，最深叶全部落在那一侧，那一侧子树的答案原封不动就是当前子树的答案。高度则统一取两侧较大值加一。递归结束后，根节点返回的 ansNode 即为全树答案。

解题步骤

第一步，为空节点约定返回 (null, 0)。之所以深度取 0 而不是 -1，是为了让叶子节点自然得到 (自己, 1)：叶子的左右都是空，两侧深度相等触发第一条分支，返回节点就是叶子本身——这正符合「单个叶子的最近公共祖先是它自己」的语义，不需要为叶子写任何特判。

第二步，先递归左子树再递归右子树，拿到两份结果之后才处理当前节点。顺序必须是后序，因为当前节点的判断依赖子树高度，而高度只有在子树全部处理完之后才能确定；写成先序或中序都会拿到未完成的信息。

第三步，比较 left.depth 与 right.depth 决定返回哪一个候选。相等时返回当前 node，原因是两侧都存在同样深的叶子，任何比 node 更低的节点都只能待在一侧，无法覆盖另一侧；不相等时返回较深那侧的候选，原因是较浅那侧的所有叶子深度都严格更小，根本不属于「最深叶」集合，把当前节点作为答案只会让它无谓地变高。

第四步，深度一律返回 max(left.depth, right.depth) + 1。这一步与候选的选取分离开写，可以避免在三个分支里各写一套加一逻辑导致口径不一致。最后在入口处只取根节点结果里的节点字段返回。

以 root = [3,5,1,6,2,0,8,null,null,7,4] 走一遍：这棵树根为 3，左子树根 5（孩子 6 和 2，2 的孩子是 7 和 4），右子树根 1（孩子 0 和 8）。递归到 6，左右皆空，深度相等返回 (6,1)；同理 7 返回 (7,1)、4 返回 (4,1)。回到节点 2，左右深度都是 1，相等，返回 (2,2)。回到节点 5，左边是 (6,1)，右边是 (2,2)，右更深，透传右侧候选，返回 (2,3)。右子树这边，0 返回 (0,1)，8 返回 (8,1)，回到节点 1 时两侧深度相等，返回 (1,2)。最后回到根 3，左侧深度 3，右侧深度 2，左更深，返回左侧候选 (2,4)。最终答案是节点 2——它恰好是最深叶 7 和 4 的最近公共祖先，而深度只有 2 的节点 0、8 被正确地排除在最深叶集合之外。

代码实现

class Solution {
    // 后序遍历天然适合这个问题：先拿到左右子树信息，再决定当前节点是否成为答案。
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        return dfs(root).node;
    }

    private Result dfs(TreeNode node) {
        if (node == null) {
            return new Result(null, 0);
        }

        Result left = dfs(node.left);
        Result right = dfs(node.right);
        if (left.depth == right.depth) {
            return new Result(node, left.depth + 1);
        }
        if (left.depth > right.depth) {
            return new Result(left.node, left.depth + 1);
        }
        return new Result(right.node, right.depth + 1);
    }

    private static class Result {
        private final TreeNode node;
        private final int depth;

        Result(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }
}

func lcaDeepestLeaves(root *TreeNode) *TreeNode {
    // 后序遍历天然适合这个问题：先拿到左右子树信息，再决定当前节点是否成为答案。
    node, _ := dfs(root)
    return node
}

func dfs(node *TreeNode) (*TreeNode, int) {
    if node == nil {
        return nil, 0
    }

    leftNode, leftDepth := dfs(node.Left)
    rightNode, rightDepth := dfs(node.Right)
    if leftDepth == rightDepth {
        return node, leftDepth + 1
    }
    if leftDepth > rightDepth {
        return leftNode, leftDepth + 1
    }
    return rightNode, rightDepth + 1
}

复杂度分析

时间复杂度：$O(n)$，其中 n 表示二叉树节点数。每个节点只在后序遍历中被访问一次，节点内部的比较与构造返回值都是常数级操作，没有任何子树高度被重复计算。

空间复杂度：$O(n)$，递归栈深度等于树高，最坏情况下树退化成链，树高为 n；返回的二元组只占常数空间，不额外累积。

关键点总结

当「答案」和「用来判定答案的辅助量」必须同时得到时，把递归返回值扩展成元组是最直接的手段。这里的元组是 (候选祖先, 子树高度)，扩展返回值把两趟遍历压成一趟，这个套路在树形问题里可以反复迁移。

递归返回值的语义要先定死再写代码。本题的不变量是「dfs(node) 返回的永远是以 node 为根的这棵子树自己的完整答案」，只要每个分支都维持这一条，正确性就是自动的，不需要额外的全局变量兜底。

空节点返回 0 而不是 -1 是有意为之的设计：它让叶子节点自动落入「左右相等」分支，从而省掉一整个特判。面试时主动说出这个选择，比写完再解释更能体现对边界的掌控。

面试视角上，面试官关心的是你能否从「两趟求解」自然过渡到「一趟返回元组」，并清楚说明为什么较浅一侧的候选可以直接丢弃。能把「最深叶集合只由最大深度决定」这句话讲明白，这题基本就过了。

Java 里用私有静态内部类承载返回值，Go 里直接用多返回值，两者表达的是同一个状态。选择贴合语言习惯的表达方式，而不是在 Java 里硬用数组去模拟元组，是代码可读性上的加分项。

易错点总结

错误写法：空节点返回深度 -1 → 叶子节点的左右深度是 -1 和 -1，仍然相等所以候选没错，但整棵树的高度整体偏移一位，如果后续还想用这个深度和别的量比较就会全错；单节点树时返回深度 0，容易被误判成空树。

错误写法：先算 maxDepth，再在第二趟里对每个节点重新调用 height() 判断 → 对用例 [1,2,null,3,null,4,null,5] 这种退化成链的树，每层都要重算一次子树高度，整体退化到 $O(n^2)$，n 到上限时明显变慢。

错误写法：左右深度不等时仍然返回当前 node → 对用例 [3,5,1,6,2,0,8,null,null,7,4]，在根节点处会直接返回节点 3，而正确答案是节点 2，答案被抬高到了不必要的位置。

错误写法：写成先序遍历，在进入子树前就想决定当前节点是不是答案 → 此时左右子树高度都还没算出来，判断条件读到的是未初始化值，对任意非平凡用例都会返回错误节点。

错误写法：只返回深度，用一个全局变量记录答案，并在深度相等时无条件覆盖它 → 对用例 [1,2,3,4,null,null,null]，节点 3 和节点 4 都会触发「左右相等」，全局变量最后被浅层节点覆盖成 3，而正确答案是 4。

错误写法：深度较大侧返回时误写成 new Result(left.node, right.depth + 1)，节点取左边深度取右边 → 对用例 [1,2,null,3]，根节点返回的深度变成 1 而不是 3，上层若还有节点会据此做出错误的分支选择。

错误写法：把「左右相等」判断写成 left.depth >= right.depth 合并成两个分支 → 相等时会返回 left.node 而不是当前节点，对用例 [1,2,3] 返回节点 2，而正确答案是节点 1。

错误写法：Java 中直接 return dfs(root).node 但 dfs 对空树返回的 Result 里 node 为 null 却忘了 Result 本身非空的约定，改成对空子树返回 null 引用 → 递归中访问 left.depth 立刻抛空指针异常，任何含单孩子节点的用例都会崩。

错误写法：Go 中把 dfs 写成只返回 *TreeNode，深度靠外部 map 缓存 → 对同一棵树的多次调用之间 map 未清空，或键用节点值而树中值虽唯一但递归顺序依赖缓存命中，行为变得不可预测且完全没有必要。

相似题目

题目	难度	考察点
236. 二叉树的最近公共祖先	中等	目标是两个给定节点，递归返回值退化为单个节点
235. 二叉搜索树的最近公共祖先	中等	利用 BST 有序性直接按值比较走单条路径，无需回溯
1676. 二叉树的最近公共祖先 IV	中等	目标集合是给定的节点数组，用哈希集合判定命中
1644. 二叉树的最近公共祖先 II	中等	目标节点可能不存在，必须额外统计命中个数
1650. 二叉树的最近公共祖先 III	中等	有父指针，转化为两条链表求相交点
104. 二叉树的最大深度	简单	本题返回元组中深度分量的裸版本
543. 二叉树的直径	简单	同样在后序中合并左右高度，但答案是路径长度而非节点
687. 最长同值路径	中等	后序返回值需附加节点值相等的约束才能向上延伸
111. 二叉树的最小深度	简单	取 min 时必须排除空子树，边界与本题取 max 相反
549. 二叉树最长连续序列 II	中等	后序返回值扩成递增与递减两个分量
113. 路径总和 II	中等	信息自顶向下传递，靠回溯维护路径而非向上返回