【力扣】257. 二叉树的所有路径

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

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

示例 1：

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

示例 2：

输入：root = [1]
输出：["1"]

提示：

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

题解：

递归法：

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

迭代法（双队列）：

func binaryTreePaths(root *TreeNode) []string {
	var result []string
	qNode := list.New()
	qPaths := list.New()
	qNode.PushBack(root)
	qPaths.PushBack(strconv.Itoa(root.Val))
	for qNode.Len() > 0 {
		node := qNode.Remove(qNode.Front()).(*TreeNode)
		paths := qPaths.Remove(qPaths.Front()).(string)
		if node.Left == nil && node.Right == nil {
			result = append(result, paths)
			continue
		}
		if node.Left != nil {
			qNode.PushBack(node.Left)
			qPaths.PushBack(paths + "->" + strconv.Itoa(node.Left.Val))
		}
		if node.Right != nil {
			qNode.PushBack(node.Right)
			qPaths.PushBack(paths + "->" + strconv.Itoa(node.Right.Val))
		}
	}
	return result
}