Binary Tree Maximum Path Sum
Problem Statement
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.
Constraints:
- The number of nodes in the tree is in the range [1, 3 * 10^4]
- -1000 <= Node.val <= 1000
Input Format:
- The root of a binary tree
Output Format:
- Return the maximum path sum of any non-empty path
Examples:
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.
Example 3:
Input:
root = [1]
Output:
1
Explanation:
The optimal path is just the single node with a path sum of 1.
Example 4:
Input:
root = [-3]
Output:
-3
Explanation:
The optimal path is just the single node with a path sum of -3.
Solutions
Recursive DFS Approach
Use recursion to compute the maximum path sum for each subtree, keeping track of the global maximum path sum that might include a turning point at any node.
Bottom-up Dynamic Programming Approach
Use a bottom-up dynamic programming approach to compute the maximum path sum for each subtree, which is equivalent to the recursive approach but more explicit in its description.
Algorithm Walkthrough
Example input: nums = []
Step-by-step execution:
- Start with root = -10
- Calculate maxPathSum for left child = 9:
- 9 has no children, so leftMax = 0, rightMax = 0
- currentPathSum = 9 + 0 + 0 = 9
- maxSum = max(-Infinity, 9) = 9
- Return 9 + max(0, 0) = 9
- Calculate maxPathSum for right child = 20:
- Calculate maxPathSum for 20's left child = 15:
- 15 has no children, so leftMax = 0, rightMax = 0
- currentPathSum = 15 + 0 + 0 = 15
- maxSum = max(9, 15) = 15
- Return 15 + max(0, 0) = 15
- Calculate maxPathSum for 20's right child = 7:
- 7 has no children, so leftMax = 0, rightMax = 0
- currentPathSum = 7 + 0 + 0 = 7
- maxSum = max(15, 7) = 15
- Return 7 + max(0, 0) = 7
- leftMax = max(0, 15) = 15, rightMax = max(0, 7) = 7
- currentPathSum = 20 + 15 + 7 = 42
- maxSum = max(15, 42) = 42
- Return 20 + max(15, 7) = 20 + 15 = 35
- For root, leftMax = max(0, 9) = 9, rightMax = max(0, 35) = 35
- currentPathSum = -10 + 9 + 35 = 34
- maxSum = max(42, 34) = 42
- Return -10 + max(9, 35) = -10 + 35 = 25
- Final result: maxSum = 42
Hints
Hint 1
Hint 2
Hint 3
Video Tutorial
Video tutorials can be a great way to understand algorithms visually
Visualization
Visualize the binary tree and highlight the maximum path sum path through the tree.
Key visualization elements:
- current node
- maximum path
- current path sum
- global maximum
Implementation Notes
This is a challenging tree problem that tests understanding of tree traversal and recursive thinking. The key insight is to handle the concept of a 'turning point' in the path, where we include both left and right subtrees in calculating the maximum path sum.