题目

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

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

示例 1：

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

示例 2：

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

提示：

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

方法一：深度优先搜索

思路及解法

最直观的方法是使用深度优先搜索。在深度优先搜索遍历二叉树时，我们需要考虑当前的节点以及它的孩子节点。

• 如果当前节点不是叶子节点，则在当前的路径末尾添加该节点，并继续递归遍历该节点的每一个孩子节点。
• 如果当前节点是叶子节点，则在当前路径末尾添加该节点后我们就得到了一条从根节点到叶子节点的路径，将该路径加入到答案即可。

如此，当遍历完整棵二叉树以后我们就得到了所有从根节点到叶子节点的路径。当然，深度优先搜索也可以使用非递归的方式实现，这里不再赘述。

代码

class Solution {
    func binaryTreePaths(_ root: TreeNode?) -> [String] {
        var paths: [String] = []
        constructPaths(root, "", &paths)
        return paths
    }
    
    func constructPaths(_ root: TreeNode?, _ path: String, _ paths: inout [String]) {
        if nil != root {
            var path = path
            path += String(root!.val)
            if nil == root?.left && nil == root?.right {
                paths.append(path)
            } else {
                path += "->"
                constructPaths(root?.left, path, &paths)
                constructPaths(root?.right, path, &paths)
            }
        }
    }
}

复杂度分析

• 时间复杂度：�(�2)O(N2)，其中 �N 表示节点数目。在深度优先搜索中每个节点会被访问一次且只会被访问一次，每一次会对 ���ℎpath 变量进行拷贝构造，时间代价为 �(�)O(N)，故时间复杂度为 �(�2)O(N2)。

• 空间复杂度：�(�2)O(N2)，其中 �N 表示节点数目。除答案数组外我们需要考虑递归调用的栈空间。在最坏情况下，当二叉树中每个节点只有一个孩子节点时，即整棵二叉树呈一个链状，此时递归的层数为 �N，此时每一层的 ���ℎpath 变量的空间代价的总和为 �(∑�=1��)=�(�2)O(∑i=1Ni)=O(N2) 空间复杂度为 �(�2)O(N2)。最好情况下，当二叉树为平衡二叉树时，它的高度为 log⁡�logN，此时空间复杂度为 �((log⁡�)2)O((logN)2)。

方法二：广度优先搜索

思路及解法

我们也可以用广度优先搜索来实现。我们维护一个队列，存储节点以及根到该节点的路径。一开始这个队列里只有根节点。在每一步迭代中，我们取出队列中的首节点，如果它是叶子节点，则将它对应的路径加入到答案中。如果它不是叶子节点，则将它的所有孩子节点加入到队列的末尾。当队列为空时广度优先搜索结束，我们即能得到答案。

代码

class Solution {
    func binaryTreePaths(_ root: TreeNode?) -> [String] {
        var paths: [String] = []
        if nil == root {
            return paths
        }
        var node_queue: [TreeNode] = []
        var path_queue: [String] = []
        
        node_queue.append(root!)
        path_queue.append(String(root!.val))
        
        while !node_queue.isEmpty {
            let node: TreeNode? = node_queue.removeFirst()
            let path: String = path_queue.removeFirst()
            
            if nil == node?.left && nil == node?.right {
                paths.append(path)
            } else {
                if nil != node?.left {
                    node_queue.append(node!.left!)
                    path_queue.append(path + "->" + String(node!.left!.val))
                }
                
                if nil != node?.right {
                    node_queue.append(node!.right!)
                    path_queue.append(path + "->" + String(node!.right!.val))
                }
            }
        }
        return paths
    }
}

复杂度分析

• 时间复杂度：�(�2)O(N2)，其中 �N 表示节点数目。分析同方法一。

• 空间复杂度：�(�2)O(N2)，其中 �N 表示节点数目。在最坏情况下，队列中会存在 �N 个节点，保存字符串的队列中每个节点的最大长度为 �N，故空间复杂度为 �(�2)O(N2)。