LeetCode.297.二叉树的序列化与反序列化（困难）

题目

LeetCode.297.二叉树的序列化与反序列化（困难）

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

题解

解法1：广度优先搜索

序列化

• 按照层序遍历记录节点值，拼接成字符串，节点之间用空格分隔。
• 空节点记为#，以便识别节点没有子树了。

反序列化

• 拆解字符串为节点列表。
• 反序列化跟序列化顺序保持一致，也是层序遍历，才能识别出节点位置。
• 按照层序遍历的过程，构建二叉树。

class Codec() {
    // Encodes a URL to a shortened URL.
    fun serialize(root: TreeNode?): String {
        if (root == null) return ""
        val nullNode = TreeNode(0)
        val sb = StringBuilder()
        val queue = java.util.ArrayDeque<TreeNode>()
        queue.add(root)
        while (queue.isNotEmpty()) {
            val node = queue.poll()
            if (node != nullNode) {
                sb.append(node.`val`)
                queue.add(node.left ?: nullNode)
                queue.add(node.right ?: nullNode)
            } else {
                sb.append("#")
            }
            sb.append(" ")
        }
        return sb.toString()
    }

    // Decodes your encoded data to tree.
    fun deserialize(data: String): TreeNode? {
        if (data.isEmpty()) return null

        val nodes = data.split(" ")
        val queue = java.util.ArrayDeque<TreeNode>()

        val root = nodes[0].toNode()!!
        queue.add(root)

        var i = 1
        while (queue.isNotEmpty() && i < nodes.size) {
            val node = queue.poll()

            val left = nodes[i].toNode()
            node.left = left
            if (left != null) {
                queue.add(left)
            }
            i++

            val right = nodes[i].toNode()
            node.right = right
            if (right != null) {
                queue.add(right)
            }
            i++
        }
        return root
    }

    private fun String.toNode(): TreeNode? {
        return if (this == "#") null
        else TreeNode(toInt())
    }
}

解法2：深度优先搜索

序列化

• 按照DFS根、左、右的遍历顺序记录节点，节点之间用空格分割。
• 遇到空节点记为#，以便在反序列化时知道没有子树了。

反序列化

• 把字符串转换为迭代器做遍历。
• 按照DFS根、左、右的遍历顺序构建二叉树。
• 遇到#说明没有子树。

class Codec() {
    // Encodes a URL to a shortened URL.
    fun serialize(root: TreeNode?): String {
        if (root == null) return ""
        val sb = StringBuilder()

        // 先序遍历
        fun dfs(root: TreeNode?) {
            if (root == null) {
                sb.append("#").append(" ")
                return
            }
            sb.append(root.`val`).append(" ")
            dfs(root.left)
            dfs(root.right)
        }

        dfs(root)

        return sb.toString().trim()
    }

    // Decodes your encoded data to tree.
    fun deserialize(data: String): TreeNode? {
        if (data.isEmpty()) return null
        val nodes = data.split(" ").map { it.toNode() }.iterator()

        fun rebuild(nodes: Iterator<TreeNode?>): TreeNode? {
            if (!nodes.hasNext()) return null
            val root = nodes.next() ?: return null
            root.left = rebuild(nodes)
            root.right = rebuild(nodes)
            return root
        }

        return rebuild(nodes)
    }


    private fun String.toNode(): TreeNode? {
        return if (this == "#") null
        else TreeNode(toInt())
    }
}