257.二叉树的所有路径

题目#257.二叉树的所有路径

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

说明:叶子节点是指没有子节点的节点。

示例:

思路分析

二叉树遍历所有路径并保存下来，这种问题属于典型的回溯法，即我们需要使用一个中间变量在遍历过程中保存遍历时经过的节点，在回到上一个节点时需要将最后一个节点删除，以保证不影响其他分支的遍历结果。
那回过头来，我们在代码中需要关注的重点是什么呢？

• 递归结束条件
  题中明确表明从“根节点”到“叶子节点”，那我们的递归结束条件就是找到叶子节点。代码的展示如下：
  root.left == null && root.right == null
  如果节点满足上诉条件，那么它就是叶子节点，在结束之前，我们需要将中间变量的值处理之后放在返回值中，并删除刚才加入中间变量的节点，以保证不影响下一层的递归，可表示为如下伪代码。
  temp.add(root.val)
// .....处理temp
temp.removeAt(temp.lastIndex)
• 递归结构体
  除了结束条件外，递归内容也是重点，为了确保二叉树的所有节点都遍历到，需要分别用左右子树当做入参，调用自己。
  dfs(root.left, ...)
dfs(root.right, ...)

代码展示

fun binaryTreePaths(root: TreeNode?): List<String> {
    if (root == null) return emptyList()
    val res = ArrayList<String>()
    dfs(res, root, ArrayList())
    return res
}

private fun dfs(res: ArrayList<String>, root: TreeNode, temp: ArrayList<Int>) {
    temp.add(root.`val`)
    if (root.left == null && root.right == null) {
        res.add(temp.joinToString("->") { it.toString() })
        temp.removeAt(temp.lastIndex)
        return
    }
    if (root.left != null) {
        dfs(res, root.left!!, temp)
    }
    if (root.right != null) {
        dfs(res, root.right!!, temp)
    }
    temp.removeAt(temp.lastIndex)
}

代码分析

在代码的11行，使用了扩展方法joinToString拼接字符串，这是kotlin中一个比较常用的高阶函数，还是十分方便的，主要功能就是能将Iterable对象经过一定的处理遍历之后拼接成字符串，拼接的连接符默认是“, ”，通过默认参数的方式给出，实际上java也有类似的方法String.join，是JDK1.8加入的，具体用法如下：
System.out.println(String.join("->", "h", "h", "h", "h"));