LeetCode 1120. 子树的最大平均值

Categories:

题目描述
思路分析
1. 解法一：后序遍历统计子树（推荐）
相似题目

题目描述

✅ 1120. 子树的最大平均值

思路分析

解法一：后序遍历统计子树（推荐）

核心思路：

后序遍历返回子树的节点和与节点数。

每个节点都可以计算自身子树平均值并更新答案。

递归向上汇总即可得到全局最大平均值。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点个数。

空间复杂度：O(h)，其中 h 表示树的高度（递归栈）。

class Solution {
    private double maxAvg = Double.NEGATIVE_INFINITY;

    public double maximumAverageSubtree(TreeNode root) {
        dfs(root);
        return maxAvg;
    }

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

        long[] left = dfs(node.left);
        long[] right = dfs(node.right);

        long sum = left[0] + right[0] + node.val;
        long count = left[1] + right[1] + 1;

        maxAvg = Math.max(maxAvg, (double) sum / count);

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

func maximumAverageSubtree(root *TreeNode) float64 {
	maxAvg := -1e18

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

		lsum, lcnt := dfs(node.Left)
		rsum, rcnt := dfs(node.Right)

		sum := lsum + rsum + int64(node.Val)
		cnt := lcnt + rcnt + 1

		avg := float64(sum) / float64(cnt)
		if avg > maxAvg {
			maxAvg = avg
		}

		return sum, cnt
	}

	dfs(root)
	return maxAvg
}

相似题目

题目	难度	考察点
104. 二叉树的最大深度	简单	DFS
543. 二叉树的直径	简单	DFS
687. 最长同值路径	中等	DFS
124. 二叉树中的最大路径和	困难	DFS
1026. 节点与其祖先之间的最大差值	中等	DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/78342313