给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1:
代码语言：javascript复制输入: [1,2,3]
1
/
2 3
输出: 6示例 2:
代码语言：javascript复制输入: [-10,9,20,null,null,15,7]
-10
/
9 20
/
15 7
输出: 42解题思路：
对于二叉树问题优先想到递归，因为划分子问题比较容易，最大路径和隐含问题是路径连续
1，由于可能含根，可能不含根，所以最大和为
max(根的值，左分支含根最大和，左分支含根最大和＋根，右分支含根最大和，右分支含根最大和＋根，左分支含根最大和＋根＋右分支含根最大和，左分支不含根最大和，右分支不含根最大和)
2，上述问题包含含根（单边）最大和子问题，求解为
max（根的值，根的值＋左含根最大和，根的值＋右含根最大和）
注意不包含：左含根最大和＋根的值＋右含根最大和，因为路线不能有分叉
代码如下
代码语言：javascript复制/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxPathSum(root *TreeNode) int {
if root==nil{
return 0
}
if root.Left!=nil && root.Right!=nil{
lr:=maxPathSumRoot(root.Left)
rr:=maxPathSumRoot(root.Right)
l:=maxPathSum(root.Left)
r:=maxPathSum(root.Right)
a:=[]int{root.Val,root.Val lr,root.Val rr,lr,rr,root.Val lr rr,l,r}
return max(a)
}else if root.Left!=nil {
lr:=maxPathSumRoot(root.Left)
l:=maxPathSum(root.Left)
a:=[]int{root.Val,root.Val lr,lr,l}
return max(a)
}else if root.Right!=nil{
rr:=maxPathSumRoot(root.Right)
r:=maxPathSum(root.Right)
a:=[]int{root.Val,root.Val rr,rr,r}
return max(a)
}
return root.Val
}
func max(arr []int) int{
max:=-1<<31
for i:=0;i<len(arr);i {
if max<arr[i]{
max=arr[i]
}
}
return max
}
func maxPathSumRoot(root *TreeNode) int {
if root==nil{
return 0
}
l:=maxPathSumRoot(root.Left)
r:=maxPathSumRoot(root.Right)
return max([]int{l root.Val,r root.Val,root.Val})
}
