HardTrees
Binary Tree Maximum Path Sum
Find max sum path in tree
Solution Approach
Post-order DFS to find max path. At each node, consider path through it and track global maximum.
Implementation
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)Complexity Analysis
Time Complexity
O(n)Space Complexity
O(h)Complexity
Time:O(n)
Space:O(h)
Asked at
GoogleAmazonMicrosoft