剑指 Offer 37. 序列化二叉树

大家好，我是程序员吴师兄，欢迎来到 图解剑指 Offer 结构化专栏，在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码，希望能帮助你即使在面试的时候紧张也能做对。

AlgoMooc 算法慕课网，每道题目都有动画和图片，致力于帮助每个程序员通过算法面试！

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列面试题37. 序列化二叉树。

题目汇总链接：https://www.algomooc.com/jianzhioffer

一、题目描述

请实现两个函数，分别用来序列化和反序列化二叉树。

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

二、题目解析

很多同学认为这道题目难，要么是因为题目一时没看明白，要么是其他人的题解分析写的太复杂、太深奥，自己一看误以为就是一道高难度的题目。

实际上这道题目不难！

一开始，我们先来解释序列化和反序列化，这两个词的概念程序员应该不会陌生，无论你是做哪方面的开发，基本上都用到过这两个操作，简单来说就是把对象转换位另外一种方便存储或者传输的形式状态，使用的时候再把该状态逆转回来。

这道题目的意思就是要我们把二叉树通过某个手段变成一个字符串的形式，同时字符串能通过另外一种手段复原为之前的二叉树，也就是说二叉树和字符串是一一对应的关系！

理解清楚题意实际上思路也就有了。

首先，思考二叉树有哪些遍历方式。

前序、中序、后序、层序。

通过这些方式都可以把二叉树转换为数组的形式，但都存在一个问题，不同的二叉树使用不同的遍历方式会生成一个相同的数组。

所以，接下来我们的思考方式就是采取哪种方式+某种手段可以生成一个特点的数组。

直接说答案：把 null 节点放进去，所有的二叉树都变成完全二叉树！

序列化过程：

• 使用广度优先搜索按照层次的顺序从上到下遍历所有的节点
• 如果当前节点不为空，以字符串的形式打印出当前节点的值，同时把它的左右子节点加入到队列中
• 如果当前节点为空，直接打印字符串 null

反序列化过程：

• 先构造出 root 入队，即字符串的第一个元素为 root
• 队列元素依次出队，构建当前元素的左右子节点，记为 node
• 遍历字符串，如果元素不为空，放入到队列中；如果元素为 null，设置为 node 的左右子节点
• 队列中的元素依次出队，设置为 node 的左右子节点

三、动画描述

四、图片描述

1、序列化过程

2、反序列化过程

五、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
public class Codec {
    public String serialize(TreeNode root) {
        // 边界条件处理
        if(root == null) return "[]";

        // 题目要求序列化后的字符串开头为 [ ,所以初始化 res 为 [
        StringBuilder res = new StringBuilder("[");

        // 生成一个队列，用来存储二叉树中的元素
        Queue<TreeNode> queue = new LinkedList<>();

        // 首先让二叉树的根节点入队
        queue.add(root);

        // 遍历队列，直到队列为空，说明访问了二叉树所有的元素
        while(!queue.isEmpty()) {

            // 队列的队首元素出队
            TreeNode node = queue.poll();

            // 如果出队的元素不为空，把它加入到序列化字符串 res 中，并以逗号结尾
            if(node != null) {
                // 加入到 res 中，以逗号结尾
                res.append(node.val + ",");
                // 在队列中添加当前元素的左节点
                queue.add(node.left);
                // 在队列中添加当前元素的右节点
                queue.add(node.right);
            }else {
                // 如果出队的元素为空，则把 null 加入到序列化字符串 res 中，并以逗号结尾
                // 这样无论输入的是什么样的二叉树，最终都变成了一颗完全二叉树
                res.append("null,");
            }
        }

        // 由于上述的遍历中的每次操作都以逗号结尾，所以此时先需要删除掉最后一个逗号
        // [ 1 , 2 , 3 ,    ---->  [ 1 , 2 , 3 
        res.deleteCharAt(res.length() - 1);

        // 序列化字符串 res 以 ] 结尾
        // [ 1 , 2 , 3     ---->  [ 1 , 2 , 3 ]
        res.append("]");
        // 返回序列化的结果
        return res.toString();
    }

    public TreeNode deserialize(String data) {
        // 边界情况判断
        if(data.equals("[]")) return null;

        // 把一个字符串分割成字符串数组，同时删除了 [ 和  ]
        // [1,2,3]  --> 1 2 3
        String[] vals = data.substring(1, data.length() - 1).split(",");

        // 二叉树的根节点为字符串的第一个元素，以此构建二叉树
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));

        // 辅助队列
        Queue<TreeNode> queue = new LinkedList<>();

        // 将根节点入队
        queue.add(root);

        // 设置一个索引，代表二叉树中的节点在字符串中的位置
        // 由于 root 已经入队，所以索引从 1 开始
        int index = 1;

        // 遍历队列，直到队列为空，说明访问了数组中的所有元素
        while(!queue.isEmpty()) {
            // 入队
            TreeNode node = queue.poll();
            // 如果字符串数组中当前索引元素不为 null，则设置为当前出队节点的左子节点
            if(!vals[index].equals("null")) {
                // 设置为当前出队节点的左子节点
                node.left = new TreeNode(Integer.parseInt(vals[index]));
                // 同时，把当前索引的节点入队
                queue.add(node.left);
            }

            // 无论字符串数组中当前索引元素是否为 null，这个元素都已经被操作了，索引向前移动，判断下一个索引元素
            index++;

            // 如果字符串数组中当前索引元素不为 null，则设置为当前出队节点的右子节点
            if(!vals[index].equals("null")) {
                // 设置为当前出队节点的右子节点
                node.right = new TreeNode(Integer.parseInt(vals[index]));
                // 同时，把当前索引的节点入队
                queue.add(node.right);
            }

            // 无论字符串数组中当前索引元素是否为 null，这个元素都已经被操作了，索引向前移动，判断下一个索引元素
            index++;
        }

        // 返回二叉树的根节点
        return root;
    }
}

六、复杂度分析

时间复杂度

序列化和反序列化的时间复杂度都为 O(N)。

空间复杂度

序列化和反序列化的空间复杂度都为 O(N)。

七、相关标签

• 树
• 深度优先搜索
• 广度优先搜索
• 字符串