LeetCode(1120) -- Maximum Average Subtree

Problem

Given the root of a binary tree, find the maximum average value of any subtree of that tree.

(A subtree of a tree is any node of that tree plus all its descendants. The average value of a tree is the sum of its values, divided by the number of nodes.)

My Solution

我在原有的树外面又包装了一层我自定义的树，记录下每个节点的平均值以及节点个数。

class Solution {
    double maxAvg;
    public double maximumAverageSubtree(TreeNode root) {
        MyTreeNode myRoot = new MyTreeNode();
        myRoot.treeNode = root;
        postOrder(myRoot);
        return maxAvg;
    }
    
    class MyTreeNode {
        MyTreeNode left;
        MyTreeNode right;
        TreeNode treeNode;
        int count;
        double avg;
    }
    
    public void postOrder(MyTreeNode myTreeNode) {
        if (myTreeNode.treeNode == null) {
            return;
        }
        myTreeNode.left = new MyTreeNode();
        myTreeNode.right = new MyTreeNode();
        myTreeNode.left.treeNode = myTreeNode.treeNode.left;
        myTreeNode.right.treeNode = myTreeNode.treeNode.right;
        
        postOrder(myTreeNode.left);
        postOrder(myTreeNode.right);
        myTreeNode.count = myTreeNode.left.count + myTreeNode.right.count + 1;
        myTreeNode.avg = (myTreeNode.left.count * myTreeNode.left.avg + myTreeNode.right.count * myTreeNode.right.avg + myTreeNode.treeNode.val) / myTreeNode.count;
        maxAvg = Math.max(maxAvg, myTreeNode.avg);
    }
}

100%

The Best Solution

class Solution {
    double ans = Double.MIN_VALUE;
    public double maximumAverageSubtree(TreeNode root) {
        helper (root);
        return ans;
    }
    public double[] helper (TreeNode root){
        if (root==null){
            return new double[]{0,0};
        }
        double [] left = helper (root.left);
        double [] right = helper (root.right);
        ans = Math.max (ans, (root.val+left[0]+right[0])/(1+left[1]+right[1]));
        return new double [] {root.val+left[0]+right[0],1+left[1]+right[1]};
    }
}

啊，不用新建什么数据结构，在helper方法中返回一个double数组，记录下所有节点的总和以及个数即可。比我的方法简化得多。