给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1：
输入：[1,2,3]
1
/ 2 3
输出：6
示例 2：
输入：[-10,9,20,null,null,15,7]
-10
/ 9 20
/ 15 7
输出：42
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。```
我的解法 ,重复了，其实最大路径是以某个节点为根节点，算左右两个最大路径，算出来的。
```python
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
if root is None:return 0
ans = root.val
max_l,max_r,max_well_l,max_well_r = -1<<31,-1<<31,-1<<31,-1<<31
if root.left is not None:
max_l = self.maxPathSum(root.left)
max_well_l = self.max_well(root.left)
if root.right is not None:
max_r = self.maxPathSum(root.right)
max_well_r = self.max_well(root.right)
ans = max(ans,max_l,max_r,max_well_l+ans,max_well_r+ans,max_well_l+max_well_r+ans)
return ans
def max_well(self, root:TreeNode)->int:
#if ‘well‘ in dir(root):
# return root.well
well = root.val
max_l = -1<<31
max_r = -1<<31
if root.left is not None:
if ‘well‘ in dir(root.left):
max_l = root.val+root.left.well
else:
max_l = root.val+self.max_well(root.left)
if root.right is not None:
if ‘well‘ in dir(root.right):
max_r = root.val+root.right.well
else:
max_r = root.val+self.max_well(root.right)
well = max(well,max_l,max_r)
root.well = well
return well
# 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 = right
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
res = [float(‘-inf‘)]
self.dfs(root, res)
return res[0] if res[0]!=float(‘-inf‘) else 0
def dfs(self, node, res):
if not node:
return 0
left = max(0, self.dfs(node.left, res))
right = max(0, self.dfs(node.right, res))
res[0] = max(res[0], left+right+node.val)
return max(left, right) + node.val
原文：https://www.cnblogs.com/Lzqayx/p/13738606.html