LeetCode 865. 具有所有最深节点的最小子树

2020-08-23 HGNULB 约 10 分钟

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

分类

题目描述

✅ 865. 具有所有最深节点的最小子树

题意分析

给一棵二叉树，先找出所有深度最大的节点（可能不止一个），再找出包含它们全部的那棵最小子树，返回这棵子树的根。这里的「子树」指某个节点连同它的全部后代。

第一层转译：一棵子树包含若干指定节点，且要尽可能小，等价于求这些节点的最近公共祖先。因为任何包含它们的子树，其根必然是它们的公共祖先；子树越小根越深，最小的那个就是最深的公共祖先。所以题目实质是「所有最深节点的 LCA」。

第二层转译，也是让这题变简单的关键：不需要真的把最深节点找出来再求 LCA。深度信息本身就能指路——对任意节点，如果它左右子树的最大深度相等，说明最深的那一层同时出现在两边，答案就必须是它自己；如果一边更深，最深节点全在那一边，答案就落在那一边的子树里，与另一边无关。

约束里节点数最多 500，$O(n)$ 或 $O(n^2)$ 都能过，但既然一次后序遍历就能同时算出深度和答案，没有理由分两趟。

边界：树只有一个节点时它自己就是答案；某节点只有一个孩子时，空侧深度为 0，必然浅于非空侧，答案往非空侧走；整棵树是一条链时答案是链尾的叶子。注意答案未必是叶子，也未必是根。

解法：后序 DFS（返回答案节点 + 深度）

核心思路

朴素做法是分两趟：先 BFS 求出最大深度并收集该层的所有节点，再对这批节点求 LCA。求多个节点的 LCA 通常要么两两递推、要么再写一遍带路径回溯的搜索，代码量翻倍，还要处理「只有一个最深节点」的退化情况。

瓶颈在于：我们把「找最深节点」和「求公共祖先」当成了两件事，于是不得不把中间结果存下来传递。但这两件事其实可以在同一次遍历里完成——深度是自底向上聚合的，答案也是自底向上聚合的，正好都能靠后序遍历的返回值携带。

于是设计一个二元返回值：dfs(node) 返回 (node, depth)，其中 depth 是以 node 为根的子树的最大深度（空树为 0），ansNode 是这棵子树内部所有最深节点的 LCA。

不变量：对任意节点 x，dfs(x) 返回的 depth 恒等于 x 子树的高度，返回的 ansNode 恒等于「x 子树中深度等于该高度的全部节点的最近公共祖先」。这个定义对空树也成立（深度 0，答案为空）。

递推关系分三种情况，全部由左右子树的深度比较决定。左右深度相等时，两侧各自的最深层处在同一绝对深度，合起来的最深节点跨越两棵子树，它们的 LCA 只能是 x 本身，返回 (x, left.depth + 1)。左深右浅时，x 子树的最深节点全部来自左子树，且它们在左子树内部的 LCA 已经算好，直接上传 (left.ansNode, left.depth + 1)。右深左浅时对称。

三种情况的 depth 都是 max(left.depth, right.depth) + 1，只是在各自分支里写成了 left.depth + 1 或 right.depth + 1，含义完全一致。

空节点返回 (null, 0) 是整个递归的基石：深度 0 让它在任何比较中都不会胜出（除非对面也是空），而 null 的答案节点永远不会被真正用到——只有当两侧都为空（叶子节点）时才会走「相等」分支，而那一支返回的是 x 自己，不是 null。

解题步骤

定义返回类型 Result(node, depth)：一次遍历要带回两个信息，用小结构体（Java 内部类 / Go struct）比用成员变量做副作用更清晰，也天然线程安全、便于推理。

递归基 node == null 返回 (null, 0)：深度取 0 而不是 -1，是为了让叶子节点的两个空孩子深度相等从而走「相等」分支、返回自己。若空树取 -1，叶子仍然相等，结论不变，但后续所有深度值都要偏移一位，不如取 0 直观。

先递归左右孩子：必须是后序——当前节点的判断完全依赖两棵子树的结果，前序或中序拿不到。

left.depth == right.depth 时返回 (node, left.depth + 1)：最深节点分居两侧（或本节点是叶子、两侧都空），当前节点是唯一能同时覆盖它们的最小根。

left.depth > right.depth 时返回 (left.node, left.depth + 1)：注意上传的是左子树算出的答案节点，不是左孩子本身。这两者经常被混淆——左孩子只有在它自己就是那棵最小子树的根时才等于答案。

否则返回 (right.node, right.depth + 1)。

顶层取 dfs(root).node：根节点的结果里已经是全树的答案，不需要再做任何后处理。

以 root = [3,5,1,6,2,0,8,null,null,7,4] 走一遍。这棵树的形状是：根 3 的左孩子是 5、右孩子是 1；5 的左孩子是 6（叶子）、右孩子是 2；2 的左右孩子是 7 和 4（都是叶子）；1 的左右孩子是 0 和 8（都是叶子）。最深的节点是 7 和 4，深度 3。

dfs(6)：左右都空，深度 0 相等，返回 (6, 1)。

dfs(7)、dfs(4)：同理各返回 (7, 1) 和 (4, 1)。

dfs(2)：左右深度都是 1，相等，最深节点 7 和 4 分居两侧，返回 (2, 2)。这里 2 就是 7 与 4 的 LCA。

dfs(5)：左边 (6, 1)、右边 (2, 2)，右边更深，说明 5 子树里的最深节点全在右边，答案沿用右边算出的 2，返回 (2, 3)。注意上传的是 right.node 即节点 2，恰好等于右孩子本身，但这是巧合——它成立是因为节点 2 自己就是它那棵子树的答案。

dfs(0)、dfs(8)：各返回 (0, 1) 和 (8, 1)。

dfs(1)：两边深度都是 1，返回 (1, 2)。

dfs(3)：左边 (2, 3)、右边 (1, 2)，左边更深，返回 (2, 4)。

顶层取 .node 得节点 2，正是包含 7 和 4 的最小子树的根。

再看一个「答案不等于孩子」的用例：把上面的节点 2 再往下延伸，令 7 有一个左孩子 9。此时最深节点只有 9 一个，dfs(7) 返回 (9, 2)，dfs(2) 发现左深右浅，上传 left.node 即 9 而不是左孩子 7——如果这里误写成上传 node.left，答案会变成 7，比正确答案 9 大一层。

代码实现

class Solution {
    public TreeNode subtreeWithAllDeepest(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 {
        TreeNode node;
        int depth;

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

type result struct {
    node  *TreeNode
    depth int
}

func subtreeWithAllDeepest(root *TreeNode) *TreeNode {
    return dfs(root).node
}

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

    left := dfs(node.Left)
    right := dfs(node.Right)

    // 两侧一样深：最深节点跨越左右，当前节点就是它们的 LCA。
    if left.depth == right.depth {
        return result{node, left.depth + 1}
    }

    // 一侧更深：最深节点全在那一侧，直接上传该侧算出的答案节点。
    if left.depth > right.depth {
        return result{left.node, left.depth + 1}
    }

    return result{right.node, right.depth + 1}
}

复杂度分析

时间复杂度：$O(n)$。每个节点恰好被递归访问一次，节点内部只做常数次比较与构造，深度与答案在同一趟里算完，不需要第二次遍历。

空间复杂度：$O(h)$，$h$ 为树高，来自递归调用栈；每层栈帧只额外持有两个 Result 引用。树退化成链时 $h = n$，平衡时 $h = \log n$。

关键点总结

「包含一组节点的最小子树」就是这组节点的最近公共祖先——先把题意翻译成 LCA，后面的推导才有方向。

一趟后序遍历可以同时聚合多个自底向上的量。当发现「求答案需要先求深度」时，与其分两趟，不如让递归返回一个二元组。

递归返回值的语义必须在所有分支里保持同一个定义（这里始终是「子树高度 + 子树内最深节点的 LCA」），一旦某个分支偷偷换了含义，整套推理就崩了。

深度相等是「答案落在当前节点」的充要信号，它同时覆盖了叶子节点这一递归基，因此不需要为叶子单独写分支。

一侧更深时要上传那一侧算出的答案节点，而不是那一侧的孩子节点；这是本题最容易写错的一行。

面试视角：能主动指出「不必先找出最深节点集合再求 LCA，深度比较本身就是路标」，是这题区分度最高的一句话；面试官常追问「答案会是叶子吗」，回答是「只有当最深节点唯一时才是」。

易错点总结

一侧更深时返回 node.left / node.right：在节点 2 下挂一条长链（如 7 再带一个孩子 9）时，会返回 7 而不是 9，答案比正确子树大一层。

空节点返回的深度与答案不一致，比如返回 (node, 0)：node 此时是 null，若某分支把它当答案上传，最终会返回空指针。

只返回深度、用成员变量记录答案：多测用例连续调用时成员变量不重置，第二个用例会沿用上一次的残留答案；即便重置，也难以表达「答案属于哪棵子树」。

用前序遍历判断：进入节点时还不知道左右子树多深，[1,2,null,3] 这类不平衡树会在根节点就误判为「两侧相等」，返回根而正确答案是节点 3。

深度定义混用「节点数」与「边数」：一处返回 left.depth + 1、另一处返回 left.depth，[1,2,3] 会得出左右不等的错误结论，答案从根跑到某个孩子。

先分别求最大深度再重新遍历找 LCA，但漏掉「最深节点只有一个」的情况：[1,2] 中最深节点只有 2，两两求 LCA 的写法在集合大小为 1 时可能返回根 1，正确答案是 2。

把「最小子树」理解成「节点数最少的子树」并去比较子树规模：[3,5,1,6,2,0,8,null,null,7,4] 中节点 7 所在的子树更小，但它不包含节点 4，会漏掉一个最深节点。

忘记根节点也可能是答案：[1,2,3] 中最深节点是 2 和 3，答案就是根 1；若代码里有「答案必须比根深」之类的假设会直接答错。

Java 里 Result 写成非静态内部类：非静态内部类隐式持有外部实例，在递归里频繁创建会带来不必要的开销，且无法在静态上下文中构造。

Go 里返回 *result 却在递归基返回 nil：上层解引用 left.depth 时空指针崩溃；返回值类型用值语义的 result 更省心。

相似题目

题目	难度	考察点
1123. 最深叶节点的最近公共祖先	中等	与本题同题，可直接套用
236. 二叉树的最近公共祖先	中等	目标节点由题目直接给出，靠「左右各找到一个」判定，不涉及深度比较
104. 二叉树的最大深度	简单	只求本题返回值里的 `depth` 那一半，是这套后序聚合的最简形态
111. 二叉树的最小深度	简单	取最小值时必须排除空孩子，否则单侧子树会把答案压成 1
543. 二叉树的直径	简单	同样后序返回高度，但答案在「左高 + 右高」处更新，与返回值分离
124. 二叉树中的最大路径和	困难	返回值是「单边最大贡献」，负数要截断为 0，返回语义与答案语义不同
110. 平衡二叉树	简单	用特殊返回值 -1 表示「已失衡」，让高度与判定共用一个 `int` 返回
863. 二叉树中所有距离为 K 的结点	中等	需要先建父指针把树变成图再 BFS，说明纯自底向上聚合并非万能