題目
Given a non-empty 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 must contain at least one node and does not need to go through the root.
答案
class Solution {
int globalMax = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
recur(root);
return globalMax;
}
public int recur(TreeNode root) {
if(root == null) return 0;
// Cut negative part
int left = Math.max(0, recur(root.left));
int right = Math.max(0, recur(root.right));
int localMax = left + right + root.val;
globalMax = Math.max(globalMax, localMax);
return Math.max(left, right) + root.val;
}
}
