Thinking process - Traversal + Divide and Conquer + Result Type

similar the minimum subtree, but it needs a result type since in order the get average, we need to know the number of nodes as well

Mistakes

don't use sum / num to get avg, since 5 / 3 == 2 / 1

class ResultType {
    public int sum;
    public int num;

    public ResultType(int sum, int num) {
        this.sum = sum;
        this.num = num;
    }
}

public class Solution {
    /**
     * @param root the root of binary tree
     * @return the root of the maximum average of subtree
     */
    private TreeNode maxAvgRoot = null;
    private ResultType maxAvg = null;
    public TreeNode findSubtree2(TreeNode root) {
        if (root == null) return root;

        dfsHelper(root);

        return maxAvgRoot;
    }

    //calculate current average and find max average subtree
    private ResultType dfsHelper(TreeNode root) {
        if (root == null) {
            return new ResultType(0, 0);
        }

        ResultType left = dfsHelper(root.left);
        ResultType right = dfsHelper(root.right);

        int currNum = left.num + right.num + 1;
        int currSum = left.sum + right.sum + root.val;

        ResultType currAvg = new ResultType(currSum, currNum);

        if (maxAvg == null || maxAvg.sum * currAvg.num < currAvg.sum * maxAvg.num) {
            maxAvgRoot = root;
            maxAvg = currAvg;
        }


        return currAvg;
    }
}