Binary Tree Maximum Path Sum
Given a non-empty binary tree, return the maximum path sum. The path must start and end at any node in the tree, and the path must go through at least one node. The path sum is the sum of all node values in the path.
Constraints:
- The number of nodes in the tree is in the range [1, 3 * 10^4].
- The node values are in the range [-10^4, 10^4].
Examples:
Input: [1,2,3]
Output: 6
Explanation: The maximum path sum is 1 + 2 + 3 = 6.
Input: [-10,9,20,null,null,15,7]
Output: 42
Explanation: The maximum path sum is 20 + 15 + 7 = 42.
Solutions
Depth-First Search
Time: O(N)Space: O(H)
The solution uses a depth-first search approach to calculate the maximum path sum. It maintains a variable max to store the maximum path sum found so far. The dfs function calculates the maximum path sum for each node and updates the max variable if a larger path sum is found.
class Solution {
int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return max;
}
private int dfs(TreeNode node) {
if (node == null) return 0;
int left = Math.max(dfs(node.left), 0);
int right = Math.max(dfs(node.right), 0);
max = Math.max(max, node.val + left + right);
return node.val + Math.max(left, right);
}
}Follow-up:
What if the tree is empty?
