Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details

describe

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.
Copy the code

Note:

The number of nodes in the tree is in the range [1, 3 * 10^4].
-1000 <= Node.val <= 1000
Copy the code

parsing

A path in a binary tree is a sequence of nodes, and a node can appear in the sequence at most once. Note that the paths here can be of any length, and not all paths need to go through the root node. The sum of paths is the sum of the values of the nodes in the paths. Given the root of a binary tree, returns the maximum sum of any non-empty paths.

In fact, the pattern of a path sum must be to take a root node as the inflection point, and then to find the left path and the left path as large as possible, and the right path and as large as possible, so as to ensure that a non-empty path to find the maximum path sum. Define a recursive function DFS, here no use DFS recursive functions to solve directly, but returned to the current node to the root node is not turn down the end of one of the biggest path and, because the recursive function will traverse all the nodes, so in the traverse all the nodes at the same time, can two paths around the recursive calculation of guarantee and as large as possible at the same time, You can also update the global variable result. Calculates the maximum sum of non-empty paths. The recursive function is not important, the point is to update the result while iterating through the recursion.

answer

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):
    def __init__(self):
        self.result = -float('inf')
        
    def maxPathSum(self, root):
        self.dfs(root)
        return self.result
    
    def dfs(self, root):
        if not root: 
            return 0
        L = self.dfs(root.left)
        R = self.dfs(root.right)
        
        PathSum = root.val
        if L>=0: PathSum += L
        if R>=0: PathSum += R
        self.result = max(self.result, PathSum)
        
        if L<=0 and R<=0:
            return root.val
        else:
            return root.val + max(L, R)	
Copy the code

The results

Each node in the linked list has a Maximum Path Sum. Memory Usage: 10000 ms Given in the Python online submissions for Binary Tree Maximum Path Sum.Copy the code

Original link: leetcode.com/problems/bi…