449. 序列化和反序列化二叉搜索树 - Kotlin 深度优先搜索

Problem: 449. 序列化和反序列化二叉搜索树

思路

如果按照中序遍历打印二叉搜索树，会直接打印出顺序序列，这时该树的根节点隐藏在序列中间，整个序列的组成为：左子树序列+根节点+右子树序列，由于整个数组都是顺序的，我们无法分辨出序列的哪个是根节点。由于序列必然由这三个部分组成，关键在于按什么顺序组成这个序列。

我们已经知道，左子树中的任意一个节点都必然小于根节点，右子树的任意一个节点都必然大于根节点，那么我们实际上是可以将左子树序列和右子树序列相邻放置的，当遍历指针指向元素从小于根节点变为大于根节点时，即说明左子树的序列已经结束

那么我们直接约定：序列的第一个元素为根节点即可

每次遍历序列时由序列的第一个元素构建根节点，然后令指针i++直至指向元素大于根节点，则此时seq[1..i-1]即为左子树序列，seq[i..seq.size-1]即为右子树序列，递归上述步骤即可

复杂度

• 时间复杂度:

• 空间复杂度:

Code

class Codec() {
    // Encodes a tree to a single string.
    fun serialize(root: TreeNode?): String =
        if (root == null) ""
        else
            root.`val`.toString() +
                    (if (root.left != null) "," + serialize(root.left) else "") +
                    (if (root.right != null) "," + serialize(root.right) else "")


    // Decodes your encoded data to tree.
    fun deserialize(data: String): TreeNode? =
        if (data == "") null
        else deserialize(data.split(",").toTypedArray())


    fun deserialize(data: Array<String>): TreeNode? {
        if (data.isEmpty()) {
            return null
        }
        val root = TreeNode(data[0].toInt())
        var i = 1
        while (i < data.size && data[i].toInt() < root.`val`) {
            i++
        }
        root.left = deserialize(data.sliceArray(1 until i))
        root.right = deserialize(data.sliceArray(i until data.size))
        return root
    }
}