第二周 二叉树

二叉树中的最大路径和

这题思考的时候还是比较简单的，首先思考的最大路径和的计算逻辑，同样使用的是递归
结束逻辑：出现空节点的时候
计算逻辑：计算根节点和左右子节点之和根节点与左右较大节点的比较，返回当前较大值，累计最大值
可以通过递归的计算的节点，都是只能和左右节点中其中一个来计算的

/**
 * 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
}