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.

Note: divide conquer and then compare summary total

public class Solution {
    /*
     * @param root: the root of binary tree
     * @return: the root of the minimum subtree
     */
    public int MinSum = Int32.MaxValue；    
    public TreeNode findSubtree(TreeNode root) {
        // write your code here
       helper(root);
       return SubTreeNode;
    }

    public int helper (TreeNode root) {
     int sumValue
     if (root == null){
         return 0;
     }
     int left = helper(root.left)
     int right = helper(root.right)

     sumValue = left + right + root.val;

     if (sumValue<=MinSum){

         MinSum = sumValue;
         SubTreeNode = root;  
     }

    return sumValue;
    }
}