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

Given a binary tree, find the subtree with minimum sum. Return the root of the subtree.

Example Given a binary tree:

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

return the node 1.

解题：这题要找minimum sum，只需要用divide conquer不断更新当前最小sum的node.

public class Solution {
    private TreeNode subtree = null;
    private int subtreeSum = Integer.MAX_VALUE;
    /**
     * @param root the root of binary tree
     * @return the root of the minimum subtree
     */
    public TreeNode findSubtree(TreeNode root) {
        // Write your code here
        dfs(root);
        return subtree;
    }

    public int dfs (TreeNode node) {
        if (node == null) {
            return 0;
        }
        int sum = dfs(node.left) + dfs(node.right) + node.val;
        if( sum < subtreeSum){
            subtreeSum = sum;
            subtree = node;
        }
        return sum;
    }
}