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 .
Example 1:
Input : [1,2,3]
1
/ \
2 3
Output : 6
Example 2:
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.