[数据结构与算法]算法----二叉树的所有路径(Kotlin)--DFS--BFS

题目

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

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

示例 1：

输入：root = [1,2,3,null,5]
输出：[“1->2->5”,“1->3”]
示例 2：

输入：root = [1]
输出：[“1”]

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-tree-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解决思路

解决方法

    fun binaryTreePaths(root: TreeNode?): List<String> {
        val result = mutableListOf<String>()
        dfs(root, mutableListOf(), result)
        return result
    }

    /**
     * 1. StringBuffer.delete(path.length - 2, path.length)
     * 前包后不包
     */
    internal fun dfs(root: TreeNode?, path: MutableList<Int>, result: MutableList<String>) {
        root?.let {
            if (root.left == null && root.right == null) {
                path.add(root.`val`)
                result.add(path.joinToString("->"))
                path.removeAt(path.size - 1)
                return
            }
            path.add(root.`val`)
            root.left?.let {
                dfs(root.left, path, result)
            }

            root.right?.let {
                dfs(root.right, path, result)
            }
            path.removeAt(path.size - 1)

        }
    }

总结

1.DFS 真的是我的弱项 迭代写的太少 今天还是一晚上才做出来

2.这道题真的不错 有很多可以学习的地方 看似简单 其实不简单

3.我自己的思路也有问题 如果说维护一个字符串"->"的增加和删除是比较麻烦 但是如果不维护
每一个参数里面都传递路径就简单易懂可维护了

4.过完节回来再好好地捋一下这个题