[LintCode] Problem 628 - Maximum Subtree

Posted on | In ,

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

Note

It’s guaranteed that there is only one subtree with maximum sum and the given binary tree is not an empty tree.

Example

Input : 

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

Output : 3

Code

1
2
3
4
5
6
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private TreeNode maxTree;
private int maxSum = Integer.MIN_VALUE;

public TreeNode findSubtree(TreeNode root) {
    findSubtreeHelper(root);
    return maxTree;
}

private int findSubtreeHelper(TreeNode node) {
    if (node == null)
        return 0;

    int left = findSubtreeHelper(node.left);
    int right = findSubtreeHelper(node.right);
    int sum = left + right + node.val;

    if (maxTree == null || sum > maxSum) {
        maxTree = node;
        maxSum = sum;
    }

    return sum;
}