1. Title Description

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

2. Ideas

For any node , If the maximum and path contain the node , Then there are only two cases :

1. The one with the larger path value in the left and right subtrees （ If the maximum path sum of left or right subtrees is negative , Set to zero , Indicates that the maximum path does not pass through this subtree ） Add the value of the node and backtrack to the parent node to form the maximum path , There may not be left or right subtrees , Only the value of this node goes back .
2. Left and right subtrees are in the maximum path , Add the value of this node to form the final maximum path . namely , This node is the root of the maximum path .

2.1 python Code

# 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））

ps： A little recursive understanding （ Seek correction ）

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.