基本思路

无论使用何种「遍历方式」进行二叉树存储，为了方便，我们都需要对空节点有所表示。

其实题目本身的样例就给我们提供了很好的思路：使用层序遍历的方式进行存储，对于某个叶子节点的空节点进行存储，同时确保不递归存储空节点对应的子节点。

层序遍历

我们使用 0x3f3f3f3f 作为无效值（当然也可以不使用数字，使用某个特殊字符进行表示，只要能在反序列时有所区分即可），并建立占位节点 emptyNode 用来代指空节点（emptyNode.val = INF）。

序列化：先特判掉空树的情况，之后就是常规的层序遍历逻辑：

  1. 起始时，将 root 节点入队；
  2. 从队列中取出节点，检查节点是否有左/右节点：
    • 如果有的话，将值追加序列化字符中（注意使用分隔符），并将节点入队；
    • 如果没有，检查当前节点是否为 emptyNode 节点，如果不是 emptyNode 说明是常规的叶子节点，需要将其对应的空节点进行存储，即将 emptyNode 入队；
  3. 循环流程 ，直到整个队列为空。

反序列：同理，怎么「序列化」就怎么进行「反序列」即可：

  1. 起始时，构造出 root 并入队；
  2. 每次从队列取出元素时，同时从序列化字符中截取两个值（对应左右节点），检查是否为 INF，若不为 INF 则构建对应节点；
  3. 循环流程 ，直到整个序列化字符串被处理完（注意跳过最后一位分隔符）。

代码：

public class Codec {
    int INF = 0x3f3f3f3f;
    TreeNode emptyNode = new TreeNode(INF);
    public String serialize(TreeNode root) {
        if (root == null) return "";

        StringBuilder sb = new StringBuilder();
        // 使用队列进行层序遍历，起始先将 root 放入队列
        Deque<TreeNode> d = new ArrayDeque<>();
        d.addLast(root);
        while (!d.isEmpty()) {
            // 每次从队列中取出元素进行「拼接」，包括「正常节点」和「叶子节点对应的首位空节点」
            TreeNode poll = d.pollFirst();
            sb.append(poll.val + "_");
            // 如果取出的节点不为「占位节点」，则继续往下拓展，同时防止「占位节点」不继续往下拓展
            if (!poll.equals(emptyNode)) {
                d.addLast(poll.left != null ? poll.left : emptyNode);
                d.addLast(poll.right != null ? poll.right : emptyNode);
            }
        }
        return sb.toString();
    }

    public TreeNode deserialize(String data) {
        if (data.equals("")) return null;

        // 根据分隔符进行分割
        String[] ss = data.split("_");
        int n = ss.length;
        // 怎么序列化就怎么反序列化
        // 使用队列进行层序遍历，起始先将 root 构建出来，并放入队列
        TreeNode root = new TreeNode(Integer.parseInt(ss[0]));
        Deque<TreeNode> d = new ArrayDeque<>();
        d.addLast(root);
        for (int i = 1; i < n - 1; i += 2) {
            TreeNode poll = d.pollFirst();
            // 每次从中取出左右节点对应 val
            int a = Integer.parseInt(ss[i]), b = Integer.parseInt(ss[i + 1]);
            // 如果左节点对应的值不是 INF，则构建「真实节点」
            if (a != INF) {
                poll.left = new TreeNode(a);
                d.addLast(poll.left);
            }
            // 如果右节点对应的值不是 INF，则构建「真实节点」
            if (b != INF) {
                poll.right = new TreeNode(b);
                d.addLast(poll.right);
            }
        }
        return root;
    }
}
  • 时间复杂度：
  • 空间复杂度：

最后

这是我们「必考真题 の 精选」系列文章的第 No.93 篇，系列开始于 2021/07/01。

该系列会将牛客网中「题霸 - 面试必考真题」中比较经典而又不过时的题目都讲一遍。

在提供追求「证明」&「思路」的同时，提供最为简洁的代码。

欢迎关注，交个朋友 (｀・ω・´)