[LintCode] 628 Maximum Subtree 解题报告

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


Example
Given a binary tree:

     1
   /   \
 -5     2
 / \   /  \
0   3 -4  -5
return the node with value 3.


思路
分治法。
我们用一个全局的maxNode来存当前拥有最大subtree sum的节点。用maxWeight来存当前最大的subtree sum的值。
以当前节点为root的subtree sum，就是当前root.val加上左儿子的subtree sum和右儿子的subtree sum。这样我们把这个活儿外包给两个小弟去做，一个找root.left的，一个找root.right的。
找完以后，我们要和两个全局变量比一比，如果发现现在的subtree sum更大了，那么我们要更新maxNode和maxWeight。
完事以后，maxNode就是指向最大subtree sum的节点。


Code

public class Solution {
    /**
     * @param root the root of binary tree
     * @return the maximum weight node
     */
    private TreeNode maxNode = null;
    private int maxWeight = Integer.MIN_VALUE;
    
    public TreeNode findSubtree(TreeNode root) {
        // Write your code here
        int root_weight = helper(root);
        return maxNode;
    }
    
    public int helper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int leftWeight = helper(root.left);
        int rightWeight = helper(root.right);
        
        if (root.val + leftWeight + rightWeight > maxWeight) {
            maxNode = root;
            maxWeight = root.val + leftWeight + rightWeight;
        }
        
        return root.val + leftWeight + rightWeight;
    }
}