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
Solutions
Solution 1: Recursion
When thinking about the classic routine of recursion problems in binary trees, we consider:
Termination condition (when to terminate recursion)
Recursively process the left and right subtrees
Merge the calculation results of the left and right subtrees
For this problem, we design a function $dfs(root)$, which returns the maximum path sum of the binary tree with $root$ as the root node.
The execution logic of the function $dfs(root)$ is as follows:
If $root$ does not exist, then $dfs(root)$ returns $0$;
Otherwise, we recursively calculate the maximum path sum of the left and right subtrees of $root$, denoted as $left$ and $right$. If $left$ is less than $0$, then we set it to $0$, similarly, if $right$ is less than $0$, then we set it to $0$.
Then, we update the answer with $root.val + left + right$. Finally, the function returns $root.val + \max(left, right)$.
In the main function, we call $dfs(root)$ to get the maximum path sum of each node, and the maximum value among them is the answer.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 91011121314151617181920
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defmaxPathSum(self,root:Optional[TreeNode])->int:defdfs(root:Optional[TreeNode])->int:ifrootisNone:return0left=max(0,dfs(root.left))right=max(0,dfs(root.right))nonlocalansans=max(ans,root.val+left+right)returnroot.val+max(left,right)ans=-infdfs(root)returnans
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcmaxPathSum(root*TreeNode)int{ans:=-1001vardfsfunc(*TreeNode)intdfs=func(root*TreeNode)int{ifroot==nil{return0}left:=max(0,dfs(root.Left))right:=max(0,dfs(root.Right))ans=max(ans,left+right+root.Val)returnmax(left,right)+root.Val}dfs(root)returnans}