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.
The number of nodes in the tree is in the range [1, 3 * 10^4], -1000 <= Node.val <= 1000
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_sum