一、问题描述

给定一个二叉树的根节点 root，返回所有从根节点到叶子节点的路径。 说明: 叶子节点是指没有子节点的节点。

示例:

输入:
   1
 /   \
2     3
 \
  5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

二、方案一：递归

1、思路

• 从根节点开始，递归遍历每个节点。
• 每到达一个节点，将节点值添加到当前路径。
• 如果节点是叶子节点，将当前路径添加到结果列表。
• 回溯时，从当前路径中移除节点值。

2、代码实现

func binaryTreePaths(root *TreeNode) []string {
    var result []string
    var path []string
    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        path = append(path, strconv.Itoa(node.Val))
        if node.Left == nil && node.Right == nil {
            result = append(result, strings.Join(path, "->"))
        }
        dfs(node.Left)
        dfs(node.Right)
        path = path[:len(path)-1]
    }
    dfs(root)
    return result
}

3、复杂度分析

• 时间复杂度：O(N^2)，其中 N 是节点的数量。每个节点都需要被访问一次，每次访问都会生成一条路径，生成路径的时间复杂度是 O(N)，因此总的时间复杂度是 O(N^2)。
• 空间复杂度：O(N)，递归栈的深度是 O(N)，每个节点都需要存储一条路径，因此总的空间复杂度是 O(N^2)，但由于结果列表的空间不计入空间复杂度，实际空间复杂度是 O(N)。

三、方案二：迭代

1、思路

• 使用栈来迭代遍历二叉树。
• 每个节点存储其父节点的路径。
• 当到达叶子节点时，将路径添加到结果列表。

2、代码实现

func binaryTreePaths(root *TreeNode) []string {
    if root == nil {
        return nil
    }
    result := []string{}
    stack := []*nodePath{{node: root, path: strconv.Itoa(root.Val)}}
    for len(stack) > 0 {
        np := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if np.node.Left == nil && np.node.Right == nil {
            result = append(result, np.path)
        }
        if np.node.Right != nil {
            stack = append(stack, &nodePath{node: np.node.Right, path: np.path + "->" + strconv.Itoa(np.node.Right.Val)})
        }
        if np.node.Left != nil {
            stack = append(stack, &nodePath{node: np.node.Left, path: np.path + "->" + strconv.Itoa(np.node.Left.Val)})
        }
    }
    return result
}
type nodePath struct {
    node *TreeNode
    path string
}

3、复杂度分析

• 时间复杂度：O(N^2)，其中 N 是节点的数量。每个节点都需要被访问一次，每次访问都会生成一条路径，生成路径的时间复杂度是 O(N)，因此总的时间复杂度是 O(N^2)。
• 空间复杂度：O(N)，栈的空间复杂度是 O(N)，每个节点都需要存储一条路径，因此总的空间复杂度是 O(N^2)，但由于结果列表的空间不计入空间复杂度，实际空间复杂度是 O(N)。

四、总结

方案	时间复杂度	空间复杂度	备注
递归	O(N^2)	O(N)	代码简洁，易于理解
迭代	O(N^2)	O(N)	需要自定义结构体来存储路径信息

两种方案的时间复杂度相同，空间复杂度也相同。递归方案代码更简洁，易于理解，而迭代方案则需要自定义结构体来存储路径信息。在实际应用中，可以根据个人喜好和具体需求来选择使用哪种方案。