Max Path Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def maxPathSum(self, root: TreeNode) -> int:
    """
       1
      / \
     2   3

    Output: 6

    -10
    / \
    9  20
        /  \
    15   7

    Output: 42


    """
    max_sum = float("-inf")

    def walk(node):
        if not node:
            return 0

        left = max(0, walk(node.left))
        right = max(0, walk(node.right))

        max_sum = max(max_sum, node.val + left + right)

        return max(left, right) + node.val

    walk(root)

    return max_sum