> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/01-07-2022-1120.md).

# 01/07/2022 1120

1120\. Maximum Average Subtree

T O(N) S O(N): the worst case.

class Solution {

```
private class Result{
    int sum;
    int count;
    double maxAverage;
    
    public Result(int sum, int count, double maxAverage){
        this.sum =sum;
        this.count = count;
        this.maxAverage = maxAverage;
    }
}


public double maximumAverageSubtree(TreeNode root) {
    
    return getMaxAverage(root).maxAverage;
    
}

private Result getMaxAverage(TreeNode root){
    if (root == null){
        return new Result(0,0,0.0);
    }
    
    // divide
    Result left = getMaxAverage(root.left);
    Result right = getMaxAverage(root.right);
    
    int count = left.count + right.count + 1;
    
    int sum = left.sum + right.sum + root.val;
    
    //conquer
    double average = Math.max((double) sum / count,  Math.max(left.maxAverage, right.maxAverage));
    
    return new Result(sum, count, average);
    
    
}
```

}

For this problem, we need get the max average value for a node in the binary tree. To get the average value a node, we need to know the sum for the node and its left subtree and right subtree and also the counts of nodes in this tree.  so for one node, its sum = left.val + right.val + node.val. its counts = 1 + left.count + right.count. Then after we get the average value for this node, we compare it to left. average and right.average and get the max one.

we first create a Rersult class with 3 instance varibles int sum, int count, and double maxaverage.  Then we use divide and conquer to get the left and right subtree Results. Finally compare them and return the max Result.