LeetCode 257. 二叉树的所有路径

题目链接：LeetCode 257. 二叉树的所有路径

题意：

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

解题思路：

递归法

采用递归法，就是一个dfs的过程，在遍历过程中，记录上路径即可。

完整代码如下：

var res []string  
var path []int
func binaryTreePaths(root *TreeNode) []string {
    res = []string{}
    path = []int{}
    dfs(root)
    return res
}
func dfs(root *TreeNode){
    path = append(path,root.Val)//将当前节点加入到路径中
    if root.Left == nil && root.Right == nil{//如果当前节点是叶子节点，则将当前的路径加入到结果集中
        line := strconv.Itoa(path[0])
        for i:=1;i<len(path);i++{
            line += "->" + strconv.Itoa(path[i])//每个都转换成string类型
        }
        res = append(res,line) //放入结果集
       
    }else{//如果当前节点不是叶子节点，则递归进行即可
        if root.Left != nil{
            dfs(root.Left)
        }
        if root.Right != nil{
             dfs(root.Right)
        }
    }
    path = path[:len(path)-1]  //恢复现场
}

迭代法

本题的迭代法相对较难理解，直接放代码。

迭代法代码：

func binaryTreePaths(root *TreeNode) []string {
	stack := []*TreeNode{}
	paths := make([]string, 0)
	res := make([]string, 0)
	if root != nil {
		stack = append(stack, root)
		paths = append(paths, "")
	}
	for len(stack) > 0 {
		l := len(stack)
		node := stack[l-1]
		path := paths[l-1]
		stack = stack[:l-1]
		paths = paths[:l-1]
		if node.Left == nil && node.Right == nil {
			res = append(res, path+strconv.Itoa(node.Val))
			continue
		}
		if node.Right != nil {
			stack = append(stack, node.Right)
			paths = append(paths, path+strconv.Itoa(node.Val)+"->")
		}
		if node.Left != nil {
			stack = append(stack, node.Left)
			paths = append(paths, path+strconv.Itoa(node.Val)+"->")
		}
	}
	return res
}