LintCode 628 - Maximum Subtree

https://yeqiuquan.blogspot.com/2017/03/lintcode-628-maximum-subtree.html
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的节点。

    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;
    }

https://www.jiuzhang.com/solution/maximum-subtree/

    public TreeNode result = null;
    public int maximum_weight = Integer.MIN_VALUE;

    public TreeNode findSubtree(TreeNode root) {
        // Write your code here
        helper(root);
        
        return result;
    }

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

        if (result == null || left_weight + right_weight + root.val > maximum_weight) {
            maximum_weight = left_weight + right_weight + root.val;
            result = root;
        }

        return left_weight + right_weight + root.val;
    }
}

http://www.careercup.com/question?id=12868663
Given a binary tree, every node has a int value,  return the root node of subtree with the largest sum up value.

static class Result {
   int value;
   Node node;
}

int sumOfTree(Node root, Result max) {
   if (root == null) {
      return 0;
   }
   int leftR = sumOfTree(root.left, max);
   int rightR = sumOfTree(root.right, max);
   int sum = leftR + rightR + root.value;
   if (sum > max.value) {
      max.value = sum;
      max.node = root;
   }
   return sum;
}