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

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

示例:

1
2
3
4
5
6
7
8
9
10
11
输入:

   1
 /   \
2     3
 \
  5

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

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

有关二叉树的问题绝大多数都可以通过递归解决。先序遍历二叉树，将每个节点加在字符串的后面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int = 0) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun binaryTreePaths(root: TreeNode?): List<String> {
        val result = ArrayList<String>()
        binaryTreePaths2(root, "", result)
        return result
    }
    private fun binaryTreePaths2(root: TreeNode?, str: String, result: MutableList<String>) {
        var mStr = str
        if (root == null) return

        if (mStr.isEmpty()){
            mStr = root.`val`.toString() + ""
        }else{
            mStr += "->" + root.`val`
        }

        if (root.left != null || root.right != null) {
            binaryTreePaths2(root.left, mStr, result)
            binaryTreePaths2(root.right, mStr, result)
        } else {
            result.add(mStr)
        }
    }
    
}

发现一个问题，在leetcode上，同样的代码逻辑，同样的测试用例，Java代码17ms，Kotlin却要用352 ms，这差距有点太大了吧。