Binary Tree Maximum Path Sum
题目：
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.
The path sum of a path is the sum of the node’s values in the path.
Given the root of a binary tree, return the maximum path sum of any non-empty path.
Example 1:
Input: root = [1,2,3] Output: 6 Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.
Example 2:
Input: root = [-10,9,20,null,null,15,7] Output: 42 Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.
Constraints:
- The number of nodes in the tree is in the range
[1, 3 * 104]. -1000 <= Node.val <= 1000
Approach One:
We need to know what information we need from children to determine max path sum and what information to pass to the parent. Imagine we are at an arbitrary node and we receive two path sum from left and right children. We need to find max(left path sum + cur val, right path sum + cur val, left path sum + right path sum + cur val) and we will keep track of the max value. Since we can have negative number, we also need to compare the path sum with current node value. When we return the value to parent, we should calculate max(large path sum from children + cur val, cur val).
Time complexity: O(n)
Space complexity: O(n)
class Solution {
int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return max;
}
private int dfs(TreeNode root) {
if (root == null) return 0;
int curVal = root.val;
int left = dfs(root.left);
int right = dfs(root.right);
int curMax = Math.max(Math.max(curVal + left, curVal + right), curVal + left + right);
curMax = Math.max(curVal, curMax);
max = Math.max(max, curMax);
return Math.max(curVal + left, curVal + right) < curVal ? curVal : Math.max(curVal + left, curVal + right);
}
}
Approach Two:
Same Idea. But less verbose and cleaner
Time complexity: O(n)
Space complexity: O(n)
class Solution {
int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return max;
}
private int dfs(TreeNode root) {
if (root == null) return 0;
int leftVal = Math.max(0, dfs(root.left));
int rightVal = Math.max(0, dfs(root.right));
max = Math.max(max, leftVal + rightVal + root.val);
return root.val + Math.max(leftVal, rightVal);
}
}
