Maximum Subtree 08/10

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

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.Have you met this question in a real interview? Yes

Example

Given a binary tree:

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

return the node with value 3.

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: the root of binary tree
     * @return: the maximum weight node
     */
     
    public TreeNode res = null;
    public int TreeSum = 0;
    public TreeNode findSubtree(TreeNode root) {
        // write your code here
        
        if(root == null){
            return root;
        }
        
        dfs(root);
        
        return res;
    }
    
    
    public int dfs(TreeNode root){
        
        if(root == null){
            return 0;
        }
        
        
        int sum = dfs(root.left) + dfs(root.right) + root.val;
        
        if(sum > TreeSum){
            res = root;
            TreeSum = sum;
        }
        
        return sum;
        
    }
    
}