Binary Tree Maximum Path Sum
Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.
For example:
Given the below binary tree,
1
/ \
2 3
Return 6.
When meet negative node, compare and cut.
private int res;
private int helper(TreeNode root) {
if(root == null) return 0;
int left = helper(root.left), right = helper(root.right);
if(left < 0) {res = Math.max(left, res); left = 0;}
if(right < 0) {res = Math.max(right, res); right = 0;}
res = Math.max(left + right + root.val, res);
return Math.max(left, right) + root.val;
}
public int maxPathSum(TreeNode root) {
if(root == null) return 0;
res = root.val;
helper(root);
return res;
}