iven 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.

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root the root of binary tree
     * @return the root of the minimum subtree
     */
    TreeNode* findSubtree(TreeNode* root) {
        // Write your code here
        int minSum = INT_MAX;
        TreeNode* minRoot = nullptr;
        helper(root, minSum, minRoot);
        return minRoot;
    }


    int helper(TreeNode* root, int &minSum, TreeNode* &minRoot) {
        if (root == nullptr)
            return 0;

        int leftSum = helper(root->left, minSum, minRoot);
        int rightSum = helper(root->right, minSum, minRoot);
        if (minRoot == nullptr || leftSum + rightSum + root->val <= minSum) {
            minRoot =  root;
            minSum = leftSum + rightSum + root->val;
        }
        return leftSum + rightSum + root->val;
    }
};