124. Binary Tree Maximum Path Sum
Similar questions:
250. Count Univalue Subtrees
687. Longest Univalue Path
Time O(n), Space O(h)
Pay attention:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int max = Integer.MIN_VALUE; // important to initialize max to MIN_VALUE
public int maxPathSum(TreeNode root) {
maxPathSumHelper(root);
return max;
}
private int maxPathSumHelper(TreeNode root) {
if (root == null) {
return 0;
}
int left = Math.max(0, maxPathSumHelper(root.left)); // 考虑负数情况
int right = Math.max(0, maxPathSumHelper(root.right)); // 考虑负数情况
max = Math.max(max, left + right + root.val); // 更新 global value
return Math.max(left, right) + root.val; // 当前层返值
}
}