Problem

Given a binary tree, find the subtree with maximum average. Return the root of the subtree.

 Notice

LintCode will print the subtree which root is your return node.
It's guaranteed that there is only one subtree with maximum average.

Example
Given a binary tree:

     1
   /   \
 -5     11
 / \   /  \
1   2 4    -2 
return the node 11.

思路

    1. lNum & rNUm, lSum & rSum, lMax & rMax, lnode & rnode

    2. num = lNum + rNum, sum = lSum + rSum, max = max{sum/num, lMax, rMax}

    public TreeNode findSubtree2(TreeNode root) {
        return helper(root).maxNode;
    }

    private Result helper(TreeNode root) {
        if (root == null) {
            return new Result(0, 0, Integer.MIN_VALUE, null);
        }

        Result left = helper(root.left);
        Result right = helper(root.right);

        int sum = left.sum + right.sum + root.val;
        int num = left.num + right.num + 1;
        double max = left.max;
        TreeNode maxNode = left.maxNode;

        if (max < right.max) {
            max = right.max;
            maxNode = right.maxNode;
        }

        if (sum > max * num) {
            max = sum/ (double)num;
            maxNode = root;
        }
        return new Result(num, sum, max, maxNode);
    }

    class Result {
        int num;
        int sum;
        double max;
        TreeNode maxNode;

        public Result (int num, int sum, double max, TreeNode maxNode) {
            this.num = num;
            this.sum = sum;
            this.max = max;
            this.maxNode = maxNode;
        }
    }