LeetCode 1120. 子树的最大平均值

2026-06-25 HGNULB 约 4 分钟

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

分类

题目描述

✅ 1120. 子树的最大平均值

题意分析

一棵二叉树里，每个节点都定义了一棵「以它为根的子树」，要求在所有这些子树中找出节点平均值最大的那个平均值。注意这里的子树是完整子树，包含该节点向下的所有后代，而不是只看它和它的直接孩子。

有 n 个节点就有 n 棵候选子树，每一棵都要参与比较，单个节点自成的子树也算，所以叶子节点的平均值就是它自己的值。

约束信号是：平均值这个量本身没法直接从左右子树的平均值合并出来——两棵子树平均值分别是 3 和 5，合起来是多少完全取决于它们各有多少节点。所以必须把它拆成可合并的分量。

边界要留意：树只有一个节点时答案就是该节点的值；答案是浮点数，除法不能落在整数域；题目保证节点值非负，这一点决定了答案初值可以取 0，但换成允许负值的变体就不成立。

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

核心思路

每棵子树的平均值由节点总和与节点数共同决定。父节点必须先得到左右子树的这两个量，所以使用后序遍历，让递归函数返回 (sum, count)。

对节点 node，合并结果为：
\[sum = leftSum + rightSum + node.val\] \[count = leftCount + rightCount + 1\]
此时 sum / count 就是以当前节点为根的完整子树平均值，用它更新全局最大值。

递归契约：dfs(node) 返回 node 整棵子树的元素和与节点数；空节点返回 (0,0)。每个非空节点恰好对应题目要求比较的一棵子树，因此遍历结束后不会漏掉候选。

解题步骤

初始化全局最大平均值。

后序递归左右子树，取得各自的 sum 与 count。

加上当前节点，得到当前子树的总和与节点数。

计算当前子树平均值并更新答案。

把当前 (sum, count) 返回给父节点。

例如叶子节点 6 返回 (6,1)；若其父节点值为 4、另一子树返回 (2,1)，父子树就返回 (12,3)，并用平均值 4 参与比较。

代码实现

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)$。每个节点只被访问和合并一次。

空间复杂度：$O(h)$。递归栈深度等于树高，最坏为 $O(n)$。

关键点总结

平均值不能只靠子树平均值继续合并，必须同时保留总和与节点数。

后序遍历保证更新答案时，当前子树信息已经完整。

dfs 的返回值服务于父节点，全局变量负责汇总所有子树的最优值。

比较平均值时要做浮点除法，不能使用整数除法截断小数。

易错点总结

返回左右子树平均值再取平均：子树大小不同，平均值不能等权合并。

在遍历孩子前计算当前平均值：会漏掉后代节点，得到的不是完整子树。

先做整数除法再转浮点：5 / 2 会先变成 2，精度已经丢失。

节点数漏加当前节点：分母错误，叶子节点甚至会除以 0。

把空节点也作为候选：(0,0) 只用于递归合并，不能计算平均值。

相似题目

题目	难度	考察点
543. 二叉树的直径	简单	回传的是深度，全局答案却是左右深度之和
333. 最大二叉搜索子树	中等	回传值要多带最值和合法性标记才能判断是否为 BST
687. 最长同值路径	中等	回传单边长度，答案取左右拼接，需比对节点值
1325. 删除给定值的叶子节点	中等	后序回传的是新子树根，用于结构性修改而非统计