LeetCode 1120. 子树的最大平均值

2026-06-25 HGNULB 约 4 分钟

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

分类

LeetCode CodeTop 中等未解决会员题 5-10 腾讯

题目描述

✅ 1120. 子树的最大平均值

题意分析

比较每个节点所代表的完整子树平均值，返回最大值。子树必须包含该节点的全部后代。

解法：后序遍历汇总子树信息

核心思路

[!blue]

每个节点都对应一棵候选子树，平均值需要知道这棵子树的节点总和与节点数。让 dfs(node) 返回 (sum, count)，分别表示以 node 为根的完整子树的这两项信息；不能只返回平均值，因为左右子树的节点数不同，两个平均值不能等权相加再除以二。

先递归取得左右结果，再合并当前节点，这就是后序遍历。左右子树彼此不重叠，加上当前节点恰好构成完整子树，因此 sum = leftSum + rightSum + node.val，count = leftCount + rightCount + 1，当前子树的平均值就是 sum/count。

用当前平均值更新全局 answer，但返回给父节点的仍然是完整子树的总和与数量，而不是这棵子树中找到的最大平均值。遍历会在每个非空节点处比较一次，所有候选子树都被覆盖，最终 answer 就是最大值。

空节点返回 (0, 0)，表示没有贡献，不计算平均值。非空节点的 count 至少为 1；除法前把操作数转为浮点数，才能保留小数。题目中的节点值非负，因此答案初始化为 0 即可。

解题步骤

将答案初始化为 0，从根节点开始递归。

遇到空节点返回总和 0、数量 0；否则先取得左右子树的信息。

两侧总和加上当前节点值，两侧数量加上 1，得到当前完整子树的信息。

先转浮点再计算 sum/count，与全局答案取较大值。

返回 (sum, count) 供父节点合并；整棵树处理结束后返回全局答案。

代码实现

class Solution {
    private double answer;

    public double maximumAverageSubtree(TreeNode root) {
        answer = 0.0;
        dfs(root);

        return answer;
    }

    // 返回完整子树总和与数量，空节点的零对只参与合并
    private int[] dfs(TreeNode node) {
        if (node == null) {
            return new int[] {
                0,
                0
            };
        }

        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        int sum = left[0] + right[0] + node.val;
        // 总和与数量都要包括当前节点
        int count = left[1] + right[1] + 1;

        // 先转浮点再相除，保留完整平均值
        answer = Math.max(answer, (double) sum / count);

        return new int[] {
            sum,
            count
        };
    }
}

func maximumAverageSubtree(root *TreeNode) float64 {
    answer := 0.0

    var dfs func(*TreeNode) (int, int)
    // 返回完整子树总和与数量，空节点的零对只参与合并
    dfs = func(node *TreeNode) (int, int) {
        if node == nil {
            return 0, 0
        }

        leftSum, leftCount := dfs(node.Left)
        rightSum, rightCount := dfs(node.Right)
        sum := leftSum + rightSum + node.Val
        // 总和与数量都要包括当前节点
        count := leftCount + rightCount + 1

        // 先转浮点再相除，保留完整平均值
        average := float64(sum) / float64(count)
        if average > answer {
            answer = average
        }
        return sum, count
    }

    dfs(root)
    return answer
}

复杂度分析

时间复杂度：$O(n)$，n 为节点数，每个节点只进行一次常数时间的合并。

空间复杂度：$O(h)$，h 为树高，递归调用和保留的子树信息随递归深度增长；退化为链时为 $O(n)$。

关键点总结

[!green]

返回聚合信息服务父节点，全局答案比较每棵候选子树。

节点值非负，因此当前答案初值零足够。

易错点总结

[!yellow]

平均两个孩子平均值，会忽略子树规模。

先整数除法再转浮点，丢掉小数。

节点数量漏加自己，叶子会出现零分母。

相似题目

题目	难度	关联与区别
1373. 二叉搜索子树的最大键值和	困难	同样在子树中汇总数值，原题还要求BST且取最大和，本题无BST限制并比较平均值。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/78342313

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