leetcode/124.BinaryTreeMaximumPathSum.py at main · sunriseXu/leetcode · GitHub

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
# Definition for a binary tree node.
class TreeNode(object):
    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):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        maxValue = [-float("inf")]

        def maxPath(root):
            if not root.left and not root.right:
                maxValue[0] = max(maxValue[0], root.val)
                return root.val
            leftVal, rightVal = 0, 0
            if root.left:
                leftVal = maxPath(root.left)
                maxValue[0] = max(maxValue[0], leftVal)
            if root.right:
                rightVal = maxPath(root.right)
                maxValue[0] = max(maxValue[0], rightVal)
            # if want to link
            # root -> can link
            # left + root -> can link
            # right + root -> can link
            # left -> can not link any more, in to set
            # right -> can not link any more, in to set
            # root + left + right -> can not link any more, in to set

            # to not link case
            maxValue[0] = max(maxValue[0], leftVal+rightVal+root.val)

            # to link case
            linkMax = max(leftVal + root.val, root.val)
            linkMax = max(rightVal + root.val, linkMax)
            return linkMax
        rootVal = maxPath(root)
        return max(maxValue[0], rootVal)
v9 = TreeNode(9)
v15 = TreeNode(15)
v7 = TreeNode(7)
v20 = TreeNode(20, v15, v7)
root = TreeNode(-10, v9, v20)
s = Solution()
res = s.maxPathSum(root)