124. Binary Tree Maximum Path Sum

Tags:

• Hard
• tree

Link

Start from the leaf node, just keep update the max value

when propagate, should consider , left + node, right + node, node

But when consider the max result, also consider (left + right, node)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:

        self.M = defaultdict(list)
        self.indeg = defaultdict(int)
        self.res = float('-inf')
        self.N = {}
        self.C1 = defaultdict(lambda: 0)
        self.C2 = defaultdict(lambda: 0)


        def dfs(node, i):
            if not node:
                return

            left = dfs(node.left, 2 * i + 1)
            right = dfs(node.right, 2 * i + 2)
            current = node

            if not self.indeg[i]:
                self.indeg[i] = 0

            self.N[i] = current

            if left:
                self.M[2*i + 1].append(i)
                self.indeg[i] += 1

            if right:
                self.M[2*i + 2].append(i)
                self.indeg[i] += 1

            return current

        dfs(root, 0)
        dq = deque([key for key in self.indeg.keys() if self.indeg[key] == 0 ])

        while dq:

            lens = len(dq)

            for _ in range(lens):
                idx = dq.popleft()

                c1 = self.C1[idx]
                c2 = self.C2[idx]

                current = self.N[idx].val


                if c1 > 0:
                    current += c1
                if c2 > 0:
                    current += c2

                self.res = max(self.res, current)

                for vv in self.M[idx]:
                    self.indeg[vv] -= 1
                    cVal = self.N[idx].val + max(c1, c2, 0)
                    if self.C1[vv] == 0:
                        self.C1[vv] = cVal
                    else:
                        self.C2[vv] = cVal
                    if self.indeg[vv] == 0:
                        dq.append(vv)


        return self.res

Method 2

Make it very simple from dfs.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:


        self.res = float('-inf')

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

            left = dfs(node.left)
            right = dfs(node.right)
            current = node.val

            if left > 0:
                current += left
            if right > 0:
                current += right

            self.res = max(self.res, current)

            return node.val + max(left, right, 0)

        dfs(root)

        return self.res