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.

Have you met this question in a real interview?

Yes

Example

Given a binary tree:

     1
   /   \
 -5     11
 / \   /  \
1   2 4    -2

return the node11.

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right>;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right> = NULL;
 *     }
 * }
 */

 struct ResultType {
     int sum;
     int size;
     ResultType (int sum, int size) {
         this->sum = sum;
         this->size = size;
     }
     ResultType() : sum(0), size(0) {}
 };

class Solution {
public:
    /**
     * @param root the root of binary tree
     * @return the root of the maximum average of subtree 
     */
    TreeNode* findSubtree2(TreeNode* root) {
        // Write your code here
        TreeNode* res = nullptr;
        ResultType curMax;
        helper(root, res, curMax);
        return res;
    }

    ResultType helper(TreeNode* root, TreeNode* &res, ResultType &curMax) {
        if (root == NULL)
            return ResultType(0, 0);

        ResultType left = helper(root->left, res, curMax);
        ResultType right = helper(root->right, res, curMax);

        ResultType curNode(root->val + left.sum + right.sum, left.size + right.size + 1);

        if (res == NULL || curNode.sum * curMax.size >= curMax.sum * curNode.size) {
            curMax = curNode;
            res = root;
        }

        return curNode;
    }
};