deepSWE.io

Binary Tree Maximum Path Sum

TreeDFSHard

20 min

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.

Example

Example 1:

Input: root = [-10,9,20,null,null,15,7]

Output: 42

Constraints

The number of nodes in the tree is in the range [1, 3 * 10⁴].
-1000 ≤ Node.val ≤ 1000

Recursive Solution (DFS)

The recursive approach uses a Depth-First Search (DFS) strategy to traverse the tree and find the maximum path sum. A helper function is used to compute the maximum path sum for each node.

Algorithm Steps

Initialize a global variable max_sum to store the maximum path sum found so far.
The base case for the recursion is when a node is null, in which case we return 0.
Recursively call the function on the left and right children to get the maximum path sum for the left and right subtrees.
Update max_sum with the maximum of its current value and the sum of the current node's value and the maximum path sums of its left and right children.
Return the sum of the current node's value and the maximum of the left and right path sums.

Start: Call maxPathSum on root (-10).

Binary Tree Maximum Path Sum Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.max_sum = float('-inf')
        
        def dfs(node):
            if not node:
                return 0
            
            left_sum = max(0, dfs(node.left))
            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)
            
        dfs(root)
        return self.max_sum