Minimum Subtree

Given a binary tree, find the subtree with minimum sum. 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 minimum sum and the given binary tree is not an empty tree.

Have you met this question in a real interview?

Yes

Example

Given a binary tree:

     1
   /   \
 -5     2
 / \   /  \
0   2 -4  -5

return the node1.

public class Solution {
    /**
     * @param root the root of binary tree
     * @return the root of the maximum average of subtree
     */

    private ReturnType maAvg;

    class ReturnType {
        int sum;
        int count;
        double avg;
        TreeNode root;
        public ReturnType (int sum, int count, TreeNode root, double avg) {
            this.sum = sum;
            this.count = count;
            this.avg = avg;
            this.root = root;
        }
    }

    public TreeNode findSubtree2(TreeNode root) {
        // Write your code here

        if (root == null) {
            return null;
        }

        maAvg = new ReturnType(0, 0, null, Integer.MIN_VALUE);

        ReturnType ans = maxSubtreeHelper(root);
        return maAvg.root;
    }

    public ReturnType maxSubtreeHelper(TreeNode root) {
        if (root == null) {
            return new ReturnType(0, 0, null, Integer.MIN_VALUE);
        }

        ReturnType left = maxSubtreeHelper(root.left);
        ReturnType right = maxSubtreeHelper(root.right);

        int sum = root.val;
        int count = 1;
        sum = sum + left.sum + right.sum;
        count = count + left.count + right.count;

        double avg = (double) sum / (double) count;

        if (avg > maAvg.avg) {
            maAvg = new ReturnType(sum, count, root, avg);
        }

        return new ReturnType(sum, count, root, avg);
    }




}