``` 题目描述： Given a binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not needto go through the root. 举例： Given the below binary tree, 1 / 2 3 Return 6. 题目分析： 找从任意节点出发的任意路径的最大长度。 每个node都有可能是其他路径上的node，这种情况要max(left，right)。如此循环。 每个node都有可能作为中心node，此时要max(左侧之前的路径最长长度，左侧之前的路径最长长度，此node为中心时候的长度) 将这个分析单元递归封装，即可实现目标。 # Definition for a binary tree node. class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def dfs(self,node): ls = rs = None lmv = rmv = 0 if node.left: lmv,ls=self.dfs(node.left) lmv=max(lmv,0) if node.right: rmv,rs=self.dfs(node.right) rmv=max(rmv,0) # print(lmv,rmv,ls,rs) mv=node.val+max(lmv,rmv) sv=node.val+lmv+rmv # mv=node.val trans_list=[elem for elem in [sv,ls,rs] if elem] if not trans_list: trans_list=[0] return mv,max(trans_list) def maxPathSum(self, root): """ :type root: TreeNode :rtype: int """ if not root: return mv,smv=self.dfs(root) return max(mv,smv) if __name__=='__main__': tn=TreeNode(2) tn1=TreeNode(-1) tn2=TreeNode(-2) tn.left=tn1 tn.right=tn2 ```