1120. Maximum Average Subtree

 一刷 05/2022

Version #1 DFS recursion

Time O(N)

Space O(N)

Runtime: 3 ms, faster than 10.29% of Java online submissions for Maximum Average Subtree.

Memory Usage: 45.1 MB, less than 46.99% of Java online submissions for Maximum Average Subtree.

/**

 * 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 {

    class NodeInfo {

        int count;

        double sum;

        public NodeInfo(int count, double sum) {

            this.count = count;

            this.sum = sum;

        }

    }

    public double maximumAverageSubtree(TreeNode root) {

        double[] maxAvg = new double[1];

        helper(root, maxAvg);

        return maxAvg[0];

    }

    

    private NodeInfo helper(TreeNode root, double[] maxAvg) {

        if (root == null) {

            return new NodeInfo(0, 0);

        }

        NodeInfo leftInfo = helper(root.left, maxAvg);

        NodeInfo rightInfo = helper(root.right, maxAvg);

        int count = leftInfo.count + rightInfo.count + 1;

        double sum = root.val + leftInfo.sum + rightInfo.sum;

        maxAvg[0] = Math.max(maxAvg[0], sum / count);

        return new NodeInfo(count, sum);

    }

}