题目

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值得总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

思路

这个路径是可以从子节点到父节点再到子节点的，深度优先搜索只能解决从上到下的路径，没法解决从下到上的问题，所以这个题目可以分为两个步骤，第一步先计算每个根节点的单向最长路径，所谓单向就是从上到下的路径，第二步，由于有了第一步的结果，我们可以知道当前节点的最长复合路径有这么几种情况，当前节点的左节点单向最长路径是maxL，当前节点右子节点的最长单向路径是maxR，那么共有四中情况：

(1)sum1= root.Val

(2)sum2 = root.Val+maxL

(3)sum3 = root.Val+maxR

(4)sum4 = root.Val+maxL+maxR

我们计算这四个值哪个最大，就是以当前节点为根节点的符合最长路径

算法设计

// 节点定义
type TreeNode struct {
	Val int
	Left *TreeNode
	Right *TreeNode
}
// 记录每个节点当前的最大单方向路径
var nodeMaxPath map[*TreeNode]int
// 记录最大的符合路径
var maxComplexPath int
// 求最大符合路径的方法
func maxPathSum(root *TreeNode) int {
	if root == nil {
		return 0
	}
	maxComplexPath = root.Val
	nodeMaxPath = make(map[*TreeNode]int)
  // 首先计算每个节点的单项最大路径
	DfsMaxSinglePathSum(root)
  // 再计算每个节点的复合最大路径
	DfsMaxComplexPathSum(root)
  
	return maxComplexPath
}
// 用于计算每个节点的复合最大路径
func DfsMaxComplexPathSum(root *TreeNode)  {
	if root == nil {
		return
	}
	maxL := nodeMaxPath[root.Left]
	maxR := nodeMaxPath[root.Right]
	val1 := root.Val
	val2 := root.Val+maxL
	val3 := root.Val+maxR
	val4 := root.Val+maxL+maxR
	result := Max(val1,val2)
	result = Max(result,val3)
	result = Max(result,val4)
	if maxComplexPath < result {
		maxComplexPath = result
	}
	DfsMaxComplexPathSum(root.Left)
	DfsMaxComplexPathSum(root.Right)
}
// 用于计算每个节点的单向最大路径并把值存在上面的map中
func DfsMaxSinglePathSum(root *TreeNode) int {
	if root == nil {
		return 0
	}
	// 右边单项路径最大值
	maxR :=DfsMaxSinglePathSum(root.Right)
	// 左边单项路径最大值
	maxL :=DfsMaxSinglePathSum(root.Left)
	val1 := root.Val
	val2 := root.Val+maxL
	val3 := root.Val+maxR
	result := Max(val1,val2)
	result = Max(result,val3)
	nodeMaxPath[root] = result
	return result
}

考察点

这个主要考察对递归深搜的运用，同时又是对深搜的一个融合，需要两步深搜结合算出结果