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

2020-08-23 HGNULB 约 5 分钟

文章信息 6 个分类 · 5 个标签

分类

LeetCode CodeTop 中等 未解决 1-2 猿辅导

标签

哈希表 深度优先搜索 树 广度优先搜索 二叉树

题目描述

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

题意分析

找出一棵子树，包含原树中深度最大的全部节点，并且它的范围尽可能小，返回它的根节点。子树必须连同根的全部后代一起取，不能任意挑选几个节点；所求根就是所有最深节点的最近公共祖先。

解法：后序递归合并高度与答案

核心思路

[!blue]

当前子树的最深节点来自哪一侧，取决于左右子树的高度。因此采用后序遍历，先得到两侧结果，再把高度和答案一起合并，避免先遍历找最深层、再重新寻找公共祖先。

递归返回的 Result 包含两个量：depth 是这棵子树的高度，空树为 0、叶子为 1；node 是包含这棵子树全部最深节点的最小子树根。这里的 depth 是相对子树根计算的高度，不是节点在原树中的绝对深度。

若左右高度相等且非零，当前子树的最深节点同时出现在两侧。任何位于当前节点下方的子树都只能覆盖其中一侧，所以最近公共祖先只能是当前节点。若两侧都为空，当前节点自己就是唯一最深节点，同样返回自己。

若左右高度不同，较浅一侧没有当前子树的最深节点，全部目标都在较深一侧。该侧递归已经找到包含它们的最小子树，直接沿用它的 node 即可，不能退回到该侧的根。无论答案来自哪里，向父层报告的高度都是 max(left.depth, right.depth) + 1。

这样每次合并都同时保持高度正确、答案范围最小，处理到原根后，返回的 node 就覆盖全树全部最深节点。

解题步骤

1. 空节点返回空答案与零高度。
2. 递归取得左右子树的答案与高度。
3. 等高返回当前节点，否则沿用更深一侧的答案。
4. 高度增加一，顶层取返回的答案节点。

只有一个最深节点时，答案就是这个节点本身；上层会不断沿用该答案。整棵树只有根节点时，也由左右空树等高的分支直接处理。

代码实现

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)

    // 两侧一样深：最深节点分布在两侧；叶子两侧皆空时也返回自身。
    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)$，递归栈及活跃返回值由树高决定。

关键点总结

[!green]

• 高度用于决定方向，答案节点用于保留更深层的公共祖先。
• 更深一侧的答案不一定就是它的根。
• 叶子由左右等高分支统一处理。

易错点总结

[!yellow]

• 一侧更深时直接返回那个孩子：最深节点的公共祖先可能还在更下方。
• 只返回较大高度而丢掉答案节点：无法把已求出的最小子树上传。
• 只比较节点值：最深与大小无关。
• 把最小子树理解成任意最小叶子：必须同时包含全部最深节点。

相似题目

题目	难度	关联与区别
236. 二叉树的最近公共祖先	中等	可把所有最深节点不断合并为最近公共祖先，本题用后序同时返回深度与祖先候选更直接。
104. 二叉树的最大深度	简单	子树高度是判断最深节点落在哪一侧的基础，两侧同高时当前节点就是候选。
1123. 最深叶节点的最近公共祖先	中等	递归向上传递目标命中信息；本题定位包含所有最深节点的最小子树，该题合并最深层深度与祖先信息。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2020/38136477

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！