Find the maximum path sum in a binary tree.
O(n)
def maxPathSum(root): res = [root.val] def dfs(node): if not node: return 0 leftMax = max(dfs(node.left), 0) rightMax = max(dfs(node.right), 0) # max path WITH split res[0] = max(res[0], node.val + leftMax + rightMax) # return max path WITHOUT split return node.val + max(leftMax, rightMax) dfs(root) return res[0]