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 must contain at least one node and does not need to go through the root.
For example:
Given the below binary tree,
1
/ \
2 3
Return 6.
Solution：分治(postorder) + DP
思路： 树的53. Maximum Subarray版本
Time Complexity: O(N) Space Complexity: O(N)
Solution Code：
class Solution {
private int max_value;
public int maxPathSum(TreeNode root) {
max_value = Integer.MIN_VALUE;
dfsMax(root);
return max_value;
}
private int dfsMax(TreeNode node) {
if(node == null) return 0;
int left_max = Math.max(0, dfsMax(node.left));
int right_max = Math.max(0, dfsMax(node.right));
int cur_max = left_max + right_max + node.val;
if(cur_max > max_value) max_value = cur_max;
return Math.max(left_max, right_max) + node.val;
}
}
