越而胜己 / Beyond awesome

Link to problem: https://leetcode.com/problems/binary-tree-maximum-path-sum/

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