mediumRecursionPattern: Divide & Conquer
Maximum Path Sum in Binary Tree Solution
Problem Statement
Given the root of a binary tree, where each node contains an integer value, find the maximum possible sum of a path from any node to any other node in the tree. A path must contain at least one node and does not need to pass through the root. The path can start and end at any node in the tree.
Examples
Example 1:
Input:{"val":1,"left":{"val":2,"left":null,"right":null},"right":{"val":3,"left":null,"right":null}}
Output:6
Explanation: The path is 3 -> 1 -> 2 with a sum of 3 + 1 + 2 = 6.
Example 2:
Input:{"val":-10,"left":{"val":9,"left":null,"right":null},"right":{"val":20,"left":{"val":15,"left":null,"right":null},"right":{"val":7,"left":null,"right":null}}}
Output:42
Explanation: The maximum path sum is achieved by the path 15 -> 20 -> 7, with a sum of 15 + 20 + 7 = 42.
Example 3:
Input:{"val":1,"left":{"val":-2,"left":null,"right":null},"right":{"val":3,"left":null,"right":null}}
Output:4
Explanation: The maximum path sum is achieved by the path 1 -> 3, with a sum of 1 + 3 = 4.
Constraints
- The number of nodes in the tree is in the range [1, 3 * 10^4].
- -1000 <= Node.val <= 1000
- The tree structure is valid.
Time: O(N) Space: O(H)
Use a recursive Depth First Search (DFS) approach. For each node, calculate the maximum path sum that can be formed with the node as the highest point (potentially including its left and right children's contributions). Update a global maximum with this value. The recursive function should return the maximum path sum that can extend upwards from the current node (i.e., a path from the current node to one of its descendants).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
class Solution:
def maxPathSum(self, root) -> int:
self.max_sum = float('-inf')
def dfs(node):
if not node:
return 0
left_max = max(0, dfs(node.left))
right_max = max(0, dfs(node.right))
current_path_sum = node.val + left_max + right_max
self.max_sum = max(self.max_sum, current_path_sum)
return node.val + max(left_max, right_max)
dfs(root)
return self.max_sum