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:
[1, 3 * 104]
.-1000 <= Node.val <= 1000
This problem asks for the maximum sum of a path in a binary tree. A path can start and end at any node, and it doesn't need to pass through the root. The crucial understanding is that a maximum path may or may not include the current node as its root.
Approach:
The most efficient approach utilizes Depth-First Search (DFS) with a recursive helper function. This function explores the tree recursively, calculating the maximum path sum achievable at each node.
The recursive function, dfs()
, performs the following:
Base Case: If the current node is null
, it returns 0. This signifies the end of a branch.
Recursive Calls: It recursively calls dfs()
on the left and right children.
Maximum Path through Current Node: It calculates the maximum path sum that includes the current node. This involves:
left
). If left
is negative, we set it to 0 because including a negative path would reduce the total sum.right
). Similarly, if it's negative, we set it to 0.root.val + left + right
. This is updated in a global variable ans
to keep track of the overall maximum path sum encountered so far.Maximum Path from Current Node (to a parent): It returns the maximum path sum starting from the current node and extending upwards to a parent node. This is crucial because the maximum overall path may not use both left and right subtrees. The function returns root.val + max(left, right)
.
Main Function: The main function initializes a global variable ans
to negative infinity and then calls dfs(root)
. Finally, it returns the value of ans
.
Time and Space Complexity:
Time Complexity: O(N) - The dfs()
function visits each node in the tree exactly once. Therefore, the time complexity is linear with respect to the number of nodes (N).
Space Complexity: O(H) - The space complexity is determined by the maximum depth of the recursion stack, which is proportional to the height (H) of the tree. In the worst case (a skewed tree), H can be equal to N. In an average case balanced tree, H is log(N).
Code Implementation (Python):
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
self.max_sum = float('-inf') # Initialize with negative infinity
def dfs(node):
if not node:
return 0
left_sum = max(0, dfs(node.left)) # Ensure non-negative values
right_sum = max(0, dfs(node.right))
self.max_sum = max(self.max_sum, node.val + left_sum + right_sum)
return node.val + max(left_sum, right_sum) # Max path going up
dfs(root)
return self.max_sum
The other languages (Java, C++, Go, TypeScript, Rust, JavaScript, C#) follow a very similar structure; only syntax and standard library functions differ slightly. They all implement the same recursive DFS algorithm. Refer to the provided code snippets in the original response for the implementations in these languages.