golang 解法, 执行用时: 8 ms, 内存消耗: 5.7 MB, 提交时间: 2023-10-22 08:41:39

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maximumAverageSubtree(root *TreeNode) float64 {
    var res float64 = 0.0
    helper(root, &res)
    return res
}

func helper(node *TreeNode, res *float64) int {
    if node == nil {
        return 0
    }
    left := helper(node.Left, res)
    right := helper(node.Right, res)
    if node.Left != nil { node.Val += node.Left.Val }
    if node.Right != nil { node.Val += node.Right.Val }
    count := left + right + 1
    *res = math.Max(*res, float64(node.Val)/float64(count))
    return count
}

cpp 解法, 执行用时: 16 ms, 内存消耗: 21.8 MB, 提交时间: 2023-10-22 08:41:21

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    pair<int, int> helper(TreeNode* root, double& res) {
        if (root == NULL) return {0, 0};
        auto pl = helper(root->left, res);
        auto pr = helper(root->right, res);
        int count = pl.first + pr.first + 1;
        int sum = pl.second + pr.second + root->val;
        res = max(res, 1.0 * sum / count);
        return {count, sum};
    }
    double maximumAverageSubtree(TreeNode* root) {
        double res = 0;
        helper(root, res);
        return res;
    }
};

python3 解法, 执行用时: 44 ms, 内存消耗: 19.5 MB, 提交时间: 2023-10-22 08:40:32

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maximumAverageSubtree(self, root: TreeNode) -> float:
        ans = float('-inf')

        def dfs(node):
            nonlocal ans
            if not node:
                return 0, 0
            left_sum, left_count = dfs(node.left)
            right_sum, right_count = dfs(node.right)
            cur_sum = left_sum + right_sum + node.val
            cur_count = left_count + right_count + 1
            ans = max(ans, cur_sum / cur_count)
            return cur_sum, cur_count

        dfs(root)
        return ans

java 解法, 执行用时: 0 ms, 内存消耗: 42.2 MB, 提交时间: 2023-10-22 08:40:15

/**
 * 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 {
    double res = 0;

    public double maximumAverageSubtree(TreeNode root) {
        if (root == null) return 0;
        helper(root);
        return res;
    }

    private int[] helper(TreeNode root) {
        int[] arr = new int[2];
        if (root == null) return arr;
        int[] left = helper(root.left);
        int[] right = helper(root.right);
        //设置当前树的元素和
        arr[0] = left[0] + right[0] + root.val;
        //设置节点个数
        arr[1] = left[1] + right[1] + 1;
        //更新平均值
        res = Math.max(res,(double) arr[0] / arr[1]);
        return arr;
    }
}