Given a non empty binary tree , Return its maximum path and .
In this question , The path is defined as a starting point from any node in the tree , A sequence that reaches any node . The path contains at least one node , And it doesn't have to go through the root node .
Input : [1,2,3]
1 / \ 2 3
Output : 6
Input : [-10,9,20,null,null,15,7]
-10 / \ 9 20 / \ 15 7
Output : 42
For any node , If the maximum and path contain the node , Then there are only two cases :
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def __init__(self): # Define a result attribute self.result = float("-inf") def maxPathSum(self, root: TreeNode) -> int: if root == None: return 0 self.getMax(root) return self.result def getMax(self,root): # Define an auxiliary function if root == None: # If the current node is empty, the maximum path containing the current node is 0 return 0 # Recursively calculates the maximum path and the path provided by the left and right subtrees of the current node , If a negative , Set it to zero （ and 0 Compare ） left = max(0,self.getMax(root.left)) right = max(0,self.getMax(root.right)) # Calculate the maximum value of left and right subtrees every time , Just update the current result self.result = max(self.result,left + right + root.val) # Back to the parent node , The maximum path cannot contain two subtrees at the same time , # So we need to use the larger subtree of the left and right subtrees plus the value of the current node for backtracking return max(left,right) + root.val #（ Recursive function , What is returned is the formula needed for backtracking , Instead of returning the final result （ Like here return result））
Backtracking can often be realized by returning , When using recursive functions ,return It's not the result of function implementation
It's going back to the formula needed to go to the top （ Most of the final results are the same as those needed for backtracking ）, It may not be the final function of this function . The formula needed to go back , Take this topic for example , In defining getMax Function , What we're returning to is max（left,right）+ root.val, Because if you go back from the current node to the upper parent node , It is necessary to provide the maximum path and... Composed of the current node and a certain subtree for the upper node . And the end result result It is in the process of recursion that it is constantly updated as a function return.