binary-tree-maximum-path-sum.py

class TreeNode(object):
    max: int
    maxa: int

    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def maxPathSum(self, root: TreeNode, parent: TreeNode|None = None) -> int:
        if root.left:
            self.maxPathSum(root.left, root)
        if root.right:
            self.maxPathSum(root.right, root)

        lm = max(0, root.left.max if root.left else 0)
        rm = max(0, root.right.max if root.right else 0)
        root.max = root.val + max(lm, rm)
        maxas = [root.left and root.left.maxa, root.right and root.right.maxa, root.val + lm + rm]
        # print("... ...", maxas)
        root.maxa = max(m for m in maxas if m is not None)
        # print("...", root.val, root.maxa)
        return root.maxa


def case1():
    seven = TreeNode(7)
    fifteen = TreeNode(15)
    twenty = TreeNode(20, fifteen, seven)
    nine = TreeNode(9)
    minusten = TreeNode(-10, nine, twenty)
    return minusten


def main():
    print("case1", Solution().maxPathSum(case1()))
    # print("case2", Solution().maxPathSum(case2()))


if __name__ == "__main__":
    main()