Beyond awesome | 越而胜己

This is a recursion problem on a tree. What's peculiar about this problem is that it seems to require the use of a global variable to track the global maximum.

For a node i, let localMax(i) be the max sum path with i as the highest node. localMax(i) is the sum of its value, its left "max downward path" left(i), and its right downward path right(i). We only need to calculate the max value of all these localMax(i)s.

When each recursive call returns, we need to return to the caller our "max downward path", which is max(left(i), right(i)) + i.val, because we can only choose one path from left and right.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def maxPathSum(self, root: TreeNode) -> int:
self.globalMax = float('-inf')
self._maxPathSumHelper(root)
return self.globalMax

def _maxPathSumHelper(self, root):
if not root:
return 0
left = max(0, self._maxPathSumHelper(root.left))
right = max(0, self._maxPathSumHelper(root.right))
localMax = left + root.val + right
self.globalMax = max(self.globalMax, localMax)
return max(left, right) + root.val
You’ve successfully subscribed to Skyward
Welcome back! You’ve successfully signed in.
Great! You’ve successfully signed up.