HardLeetCode #124Trees
Binary Tree Maximum Path Sum
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. The path sum of a path is the sum of the node 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
Examples
Input: root = [-10,9,20,null,null,15,7]
Output: 42
The optimal path is 15 -> 20 -> 7 with sum = 42.
Solution
Approach
DFS returning max gain from each subtree. At each node, update global max with (left gain + node + right gain). Return node + max(left, right, 0) to parent.
def maxPathSum(root):
max_sum = float("-inf")
def dfs(node):
nonlocal max_sum
if not node:
return 0
left = max(dfs(node.left), 0)
right = max(dfs(node.right), 0)
max_sum = max(max_sum, node.val + left + right)
return node.val + max(left, right)
dfs(root)
return max_sumComplexity
Time:O(n)
Space:O(h)
Hints
- 1.Path can start and end at any node
- 2.At each node, consider path through it as potential max
- 3.Return single path contribution to parent
Asked at
Google