124. Binary Tree Maximum Path Sum (Hard)
https://leetcode.com/problems/binary-tree-maximum-path-sum/
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.
Example 1:
Input: [1,2,3] 1 / \ 2 3 Output: 6
Example 2:
Input: [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7 Output: 42
Solutions
class Solution {
private int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if (root == null) {
return 0;
}
dfs(root);
return max;
}
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
// Values for left and right can be negative, but the branch with negative outcomes
// will be cut off later
int left = dfs(root.left);
int right = dfs(root.right);
// global maximum, max used to keep the largest one
max = Math.max(max, root.val);
max = Math.max(max, root.val + left);
max = Math.max(max, root.val + right);
max = Math.max(max, root.val + left + right);
// local maximum of adjacent context path
int leftVal = Math.max(root.val, root.val + left);
int rightVal = Math.max(root.val, root.val + right);
return Math.max(leftVal, rightVal);
}
}