二叉树中的最大路径和
这题思考的时候还是比较简单的，首先思考的最大路径和的计算逻辑，同样使用的是递归
结束逻辑：出现空节点的时候
计算逻辑：计算根节点和左右子节点之和根节点与左右较大节点的比较，返回当前较大值，累计最大值
可以通过递归的计算的节点，都是只能和左右节点中其中一个来计算的
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxPathSum(root *TreeNode) int {
_,maxSum:= helper(root)
return maxSum
}
func helper(root *TreeNode)(int,int){
if root == nil{
return 0,math.MinInt32
}
leftVal,leftMax := helper(root.Left)
leftVal = max(leftVal,0)
rightVal,rightMax := helper(root.Right)
rightVal = max(rightVal,0)
newSum := root.Val + leftVal + rightVal
return root.Val + max(leftVal,rightVal), max(max(leftMax,rightMax),newSum)
}
func max (left,right int)int{
if left > right {
return left
}
return right
}
路径总和 II
这题的思路还是很清晰的，在通过简单的题目之后，这题就显得很容易，唯一需要处理的就是怎么将所有路径返回
出现了这几个问题：
1、不能使用全局变量：这里之前对结果使用全局变量，但是代码执行的逻辑，意味着结果会出现重复的问题
2、golang中出现的在二维切片中，添加切片的问题
ret = append(ret,append([]int{},singleRet...))
最终结果是这样的
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func pathSum(root *TreeNode, targetSum int) [][]int {
var(
ret [][]int
singleRet []int
)
var h func(root*TreeNode,targetSum int)
h = func(root*TreeNode,targetSum int){
if root == nil{
return
}
targetSum -=root.Val
singleRet = append(singleRet,root.Val)
defer func() {
singleRet = singleRet[:len(singleRet)-1]
}()
if root.Left == nil && root.Right ==nil && targetSum == 0{
ret = append(ret,append([]int{},singleRet...))
}
h(root.Left,targetSum)
h(root.Right,targetSum)
}
h(root,targetSum)
return ret
}
