257. 二叉树的所有路径

题目描述

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [1,2,3,null,5]
输出：[“1->2->5”,“1->3”]

示例 2：

输入：root = [1]
输出：[“1”]

提示：

树中节点的数目在范围 [1, 100] 内
-100 <= Node.val <= 100

解法一：递归

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


func binaryTreePaths(root *TreeNode) []string {
    var res []string
    if root == nil {
        return res
    }
    var cur []string
    var dfs func(root *TreeNode)
    dfs = func(root *TreeNode) {
        if root.Left == nil && root.Right == nil {
            cur = append(cur, fmt.Sprintf("%d", root.Val))
            res = append(res, strings.Join(cur, "->"))
            cur = cur[:len(cur)-1]
            return
        }
        cur = append(cur, fmt.Sprintf("%d", root.Val))
        if root.Left != nil {
            dfs(root.Left)
        }
        if root.Right != nil {
            dfs(root.Right)
        }
        cur = cur[:len(cur)-1]
    }
    dfs(root)
    return res
}

官方题解如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


var paths []string

func binaryTreePaths(root *TreeNode) []string {
    paths = []string{}
    constructPaths(root, "")
    return paths
}

func constructPaths(root *TreeNode, path string) {
    if root != nil {
        pathSB := path
        pathSB += strconv.Itoa(root.Val)
        if root.Left == nil && root.Right == nil {
            paths = append(paths, pathSB)
        } else {
            pathSB += "->"
            constructPaths(root.Left, pathSB)
            constructPaths(root.Right, pathSB)
        }
    }
}

总结：

可以使用 fmt.Sprintf("%d", root.Val) 或 strconv.Itoa(root.Val) 将 root.Val 转换为字符串。