Tree Traversal Target: 15s
Bottom-up DFS. At each node: update global max with left+node+right. Return single branch for parent to use.
def maxPathSum(root):
res = [float('-inf')]
def dfs(node):
if not node: return 0
left = max(dfs(node.left), 0) # ignore negative paths
right = max(dfs(node.right), 0)
# path through this node as turning point
res[0] = max(res[0], left + node.val + right)
# return max single-side path for parent
return node.val + max(left, right)
dfs(root)
return res[0]Type it from memory. Go.