LeetCode 124. Binary tree maximum path sum - binary tree series question 8

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Example 1:

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Constraints:

• The number of nodes in the tree is in the range [1, 3 * 104].
• -1000 <= Node.val <= 1000

A path in a binary tree path Defined , A path is a sequence of nodes , Adjacent nodes are connected by an edge , Each node can only appear once in the path , The path does not have to go through the root node , It doesn't have to start or end with a leaf node . Path sum is the sum of all node values in the path . It is required to find the largest path in the tree and .

According to the above description of the path , We can know that for a node , The path with the maximum path sum passing through the node is one of the following paths ：

1） Node itself , That is, the path has only one node

2） Node itself + The path with the largest sum from the left child node down

3） Node itself + The path with the largest sum from the right child node down

4） The path with the largest sum from the left child node down +  Node itself + The path with the largest sum from the right child node down .

above 4 The path with the largest sum is the maximum sum path passing through that node , So find the maximum sum path of all nodes , Then find out the maximum path in the whole tree .

So we can use the following sequence to go through the calendar , When traversing a node , First, recursively call and wait for the left subtree to return the path with the maximum sum from the left subtree , Then recursively call and wait for the right subtree to return the path with the maximum sum from the right subtree , Then we can calculate the above described 4 The sum of the paths , Find the maximum sum . Finally, we have to put “ Node itself + The path with the largest sum from the left child node down ” and “ Node itself + The path with the largest sum from the right child node down ” The larger of is returned to the upper layer for use .

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        maxSum = -1000
        
        def helper(node):
            if not node:
                return 0
            
            nonlocal maxSum
            
            lsum = helper(node.left)
            rsum = helper(node.right)
            maxSum = max(maxSum, lsum + rsum + node.val)
            
            res = max(max(lsum + node.val, rsum + node.val), node.val)
            maxSum = max(maxSum, res)
            
            return res
        
        helper(root)
        
        return maxSum