Beyond awesome | 越而胜己

Link to problem:

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.


对某一个结点 i 来说,以 i 为“最高结点”的最大和路径 localMax(i) 是它自身的值 + 左边“往下路径”的最大和 left(i) + 右边“往下路径”的最大和 right(i)。我们只需要计算所有这些 localMax(i) 的最大值,即 globalMax 即可。回溯时结点 i 需要返回给上一层的是以 i 为最高节点的“往下路径”,即 max(left(i) + right(i)) + i.val(因为左右只能选择一支)。


# 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')
        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