257_二叉树的所有路径

类型：树

1. 二叉树的所有路径 💚
https://leetcode-cn.com/problems/binary-tree-paths/

❓ 给定一个二叉树，返回所有从根节点到叶子节点的路径。
```
输入:

   1
 /   \
2     3
```

输出: ["1->2->5", "1->3"]
```

💡  DFS

```python
# 官方实现
class Solution:
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        def construct_paths(root, path):
            if root:
                path += str(root.val)
                if not root.left and not root.right:  # 当前节点是叶子节点
                    paths.append(path)  # 把路径加入到答案中
                else:
                    path += '->'  # 当前节点不是叶子节点，继续递归遍历
                    construct_paths(root.left, path)
                    construct_paths(root.right, path)

        paths = []
        construct_paths(root, '')
        return paths
```

时间复杂度：O(n^2)，注意代码中 path 是一个字符串，而 python 中字符串变量的赋值不是引用传递，而是构造拷贝。拷贝的时间复杂度是 O(n)，每个结点遍历到一次，因此总时间复杂度为 O(n^2)。

空间复杂度：O(n^2)