Skip to content

Latest commit

 

History

History
 
 

1120.Maximum Average Subtree

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 
 
 
 
 
 
 
 
 

English Version

题目描述

给你一棵二叉树的根节点 root,找出这棵树的 每一棵 子树的 平均值 中的 最大 值。

子树是树中的任意节点和它的所有后代构成的集合。

树的平均值是树中节点值的总和除以节点数。

 

示例:

输入:[5,6,1]
输出:6.00000
解释: 
以 value = 5 的节点作为子树的根节点,得到的平均值为 (5 + 6 + 1) / 3 = 4。
以 value = 6 的节点作为子树的根节点,得到的平均值为 6 / 1 = 6。
以 value = 1 的节点作为子树的根节点,得到的平均值为 1 / 1 = 1。
所以答案取最大值 6。

 

提示:

  1. 树中的节点数介于 1 到 5000之间。
  2. 每个节点的值介于 0 到 100000 之间。
  3. 如果结果与标准答案的误差不超过 10^-5,那么该结果将被视为正确答案。

解法

方法一:递归

我们可以使用递归的方法,对于每个节点,计算以该节点为根的子树的节点和以及节点个数,然后计算平均值,与当前最大值比较,更新最大值。

因此,我们设计一个函数 $dfs(root)$,表示以 $root$ 为根的子树的节点和以及节点个数,返回值为一个长度为 $2$ 的数组,其中第一个元素表示节点和,第二个元素表示节点个数。

函数 $dfs(root)$ 的递归过程如下:

  • 如果 $root$ 为空,返回 $[0, 0]$
  • 否则,计算 $root$ 的左子树的节点和以及节点个数,记为 $[ls, ln]$;计算 $root$ 的右子树的节点和以及节点个数,记为 $[rs, rn]$。那么以 $root$ 为根的子树的节点和为 $root.val + ls + rs$,节点个数为 $1 + ln + rn$,计算平均值,与当前最大值比较,更新最大值;
  • 返回 $[root.val + ls + rs, 1 + ln + rn]$

最后,返回最大值即可。

时间复杂度 $O(n)$,空间复杂度 $O(n)$。其中 $n$ 为二叉树的节点个数。

Python3

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:
        def dfs(root):
            if root is None:
                return 0, 0
            ls, ln = dfs(root.left)
            rs, rn = dfs(root.right)
            s = root.val + ls + rs
            n = 1 + ln + rn
            nonlocal ans
            ans = max(ans, s / n)
            return s, n

        ans = 0
        dfs(root)
        return ans

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private double ans;

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

    private int[] dfs(TreeNode root) {
        if (root == null) {
            return new int[2];
        }
        var l = dfs(root.left);
        var r = dfs(root.right);
        int s = root.val + l[0] + r[0];
        int n = 1 + l[1] + r[1];
        ans = Math.max(ans, s * 1.0 / n);
        return new int[] {s, n};
    }
}

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    double maximumAverageSubtree(TreeNode* root) {
        double ans = 0;
        function<pair<int, int>(TreeNode*)> dfs = [&](TreeNode* root) -> pair<int, int> {
            if (!root) {
                return {0, 0};
            }
            auto [ls, ln] = dfs(root->left);
            auto [rs, rn] = dfs(root->right);
            int s = root->val + ls + rs;
            int n = 1 + ln + rn;
            ans = max(ans, s * 1.0 / n);
            return {s, n};
        };
        dfs(root);
        return ans;
    }
};

Go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maximumAverageSubtree(root *TreeNode) (ans float64) {
	var dfs func(*TreeNode) [2]int
	dfs = func(root *TreeNode) [2]int {
		if root == nil {
			return [2]int{}
		}
		l, r := dfs(root.Left), dfs(root.Right)
		s := root.Val + l[0] + r[0]
		n := 1 + l[1] + r[1]
		ans = math.Max(ans, float64(s)/float64(n))
		return [2]int{s, n}
	}
	dfs(root)
	return
}

...