Minimum Subtree

Description

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.

Example

Given a binary tree:

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

return the node1.

Related problems

Binary Tree Maximum Node

Easy Subtree with Maximum Average

Easy Binary Tree Longest Consecutive Sequence

Implementation

Link: http://lintcode.com/en/problem/minimum-subtree/

/**
 * 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:

    Solution () {
        subtreeSum = INT_MAX;
        subroot = NULL;
    }
    /**
     * @param root the root of binary tree
     * @return the root of the minimum subtree
     */
    TreeNode* findSubtree(TreeNode* root) {
        // Write your code here
        helper(root);
        return subroot;
    }

    int helper(TreeNode* root) {
        if (root == NULL) return 0;

        int sum = helper(root->left) + helper(root->right) + root->val;

        if (sum < subtreeSum) {
            subtreeSum = sum;
            subroot = root;
        }
    }

private:
    int subtreeSum;
    TreeNode * subroot;
};