题目

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
}

站点统计

  • 文章总数:315 篇
  • 分类总数:20 个
  • 标签总数:193 个
  • 运行天数:1147 天
  • 访问总数:26831 人次

浙公网安备33011302000604

辽ICP备20003309号