题目

leetcode257:https://leetcode-cn.com/problems/binary-tree-paths

代码与解析

• 确定函数参数及返回值
  要传入三个， 根节点， 路径path, 和要返回的数组res

• 确定递归终止条件
  root == nil
  遍历到叶子结点的条件
  root.Left==nil&&root.Right==nil

• 确定单层递归逻辑
  这里要用前序遍历，（因为中 左 右）顺序正好和要求的顺序一样
  前序遍历要先处理中间节点，于是path = append(path, root.val)
  然后要判断当前节点是否是叶子结点，如果是叶子结点，就要从路径里面取值，拼接字符串了，
  然后判断左右节点是否为空，进行递归和回溯，（因为path不能一直加入节点，还要进行删除）

func binaryTreePaths(root *TreeNode) []string {
    res := []string{}
    path := []int{}
    if root == nil {
        return res
    }
    travseral(root, &res, &path)
    return res
}
func travseral(root *TreeNode, res *[]string, path *[]int) {
    *path = append(*path, root.Val)
    if root.Left == nil && root.Right == nil {
        // 叶子结点
        spath := ""
        for i := 0; i < len(*path)-1; i++ {
            str := strconv.Itoa((*path)[i]) + "->"
            spath += str
        }
        spath += strconv.Itoa((*path)[len(*path)-1])
        *res = append(*res, spath)
        // fmt.Println(res)
        return
    }
    if root.Left != nil {
        travseral(root.Left, res, path)
        if len(*path) > 0 {
            *path = (*path)[:len(*path)-1]
        }

    }
    if root.Right != nil {
        travseral(root.Right, res, path)
        if len(*path) > 0 {
            *path = (*path)[:len(*path)-1]
        }
    }
}

或者说这样，

这样虽然看起来，传参简单了很多，但其实没有，只是作用域捣鬼罢了，
这里可能有同学有疑问， 传参进去和这样不一样吗，不一样的，传参的话，是传的值，非地址，而在函数内直接用，是在原地址改。

func binaryTreePaths(root *TreeNode) []string {
    res := []string{}
    path := []int{}
    if root == nil {
        return res
    }
    var travseral func(root *TreeNode)
    travseral = func (root *TreeNode){
        path  = append(path, root.Val)
        // fmt.Println(path)
        if root.Left==nil&&root.Right==nil{
            spath := ""
            for i:=0;i<len(path)-1;i++{
                spath += strconv.Itoa(path[i]) + "->"
            }
            spath += strconv.Itoa(path[len(path)-1])
            res= append(res, spath)
        }
        if root.Left!=nil{
            travseral(root.Left)
            if len(path)>0 {
                path = path[:len(path)-1]
            }
        }
        if root.Right!=nil{
            travseral(root.Right)
            if len(path)>0{
                path = path[:len(path)-1]
            }
        }
    }
    travseral(root)
    return res
}

或者这样

这份代码更简洁， 其实也用到了回溯，
回溯就隐藏在traversal(cur->left, path + “->”, result);中的 path + “->”。 每次函数调用完，path依然没有加上”->” ，这就是回溯了。
如果把 path + “->”作为函数参数就是可以的，因为这样并有没有改变path的数值，在执行完递归函数之后，path依然是之前的数值（这样就相当于回溯了）
具体参考carl大佬博客，往下翻，在讲迭代法之前一点

func binaryTreePaths(root *TreeNode) []string {
    if root == nil {
        return nil
    }
    var res []string
    var travseral func(root *TreeNode, path string)
    travseral = func(root *TreeNode, path string) {
        path += strconv.Itoa(root.Val)
        if root.Left == nil && root.Right == nil {
            res = append(res, path)
            return
        }
        if root.Left != nil {
            travseral(root.Left, path+"->")
        }
        if root.Right != nil {
            travseral(root.Right, path+"->")
        }
    }
    travseral(root, "")
    return res
}