携手创造，一起生长！这是我参与「日新方案 8 月更文应战」的第25天，点击查看活动详情

题目

给你一个二叉树的根节点 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)
            }
        }
    }
}

复杂度剖析

• 时刻复杂度：O(N2)O(N^2)O(N2)，其间 $N$ 表明节点数目。在深度优先查找中每个节点会被拜访一次且只会被拜访一次，每一次会对 $path$ 变量进行拷贝结构，时刻价值为 $O(N)$，故时刻复杂度为 O(N2)O(N^2)O(N2)。

• 空间复杂度：O(N2)O(N^2)O(N2)，其间 $N$ 表明节点数目。除答案数组外咱们需求考虑递归调用的栈空间。在最坏情况下，当二叉树中每个节点只要一个孩子节点时，即整棵二叉树呈一个链状，此刻递归的层数为 $N$，此刻每一层的 $path$ 变量的空间价值的总和为 O(∑i=1Ni)=O(N2)O(\sum_{i = 1}^{N} i) = O(N^2)O(∑i=1N​i)=O(N2) 空间复杂度为 O(N2)O(N^2)O(N2)。最好情况下，当二叉树为平衡二叉树时，它的高度为 $\log N$，此刻空间复杂度为 O((log⁡N)2)O((\log {N})^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
    }
}

复杂度剖析

• 时刻复杂度：O(N2)O(N^2)O(N2)，其间 $N$ 表明节点数目。剖析同办法一。

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