标题描述

这是 LeetCode 上的 297. 二叉树的序列化与反序列化 ，难度为 困难。

Tag : 「二叉树」、「层序遍历」

序列化是将一个数据结构或许目标转化为接连的比特位的操作，从而能够将转化后的数据存储在一个文件或许内存中，一起也能够通过网络传输到另一个计算机环境，采纳相反办法重构得到原数据。

请规划一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法履行逻辑，你只需求确保一个二叉树能够被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格局与 LeetCode 目前运用的办法共同，概况请参阅LeetCode 序列化二叉树的格局。你并非必须采纳这种办法，你也能够采用其他的办法处理这个问题。

示例 1：

【面试高频题】难度 1.5/5，一道全旧的普通面试题

输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

示例 2：

输入：root = []
输出：[]

示例 3：

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

示例 4：

输入：root = [1,2]
输出：[1,2]

提示：

  • 树中结点数在规模 [0,104][0, 10^4] 内
  • −1000<=Node.val<=1000-1000 <= Node.val <= 1000

基本思路

不管运用何种「遍历办法」进行二叉树存储，为了方便，咱们都需求对空节点有所表示。

其实标题自身的样例就给咱们提供了很好的思路：运用层序遍历的办法进行存储，关于某个叶子节点的空节点进行存储，一起确保不递归存储空节点对应的子节点。

层序遍历

依据节点值的数据规模 -1000 <= Node.val <= 1000（我是在 297. 二叉树的序列化与反序列化 看的，你也能够不运用数字，运用某个特别字符进行表示，只要能在反序列时有所区分即可），咱们能够建立占位节点 emptyNode 用来代指空节点（emptyNode.val = INF）。

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

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

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

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

代码：

public class Codec {
    int INF = -2000;
    TreeNode emptyNode = new TreeNode(INF);
    public String serialize(TreeNode root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        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;
        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();
            int a = Integer.parseInt(ss[i]), b = Integer.parseInt(ss[i + 1]);
            if (a != INF) {
                poll.left = new TreeNode(a);
                d.addLast(poll.left);
            }
            if (b != INF) {
                poll.right = new TreeNode(b);
                d.addLast(poll.right);
            }
        }
        return root;
    }
}
  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(n)O(n)

最终

这是咱们「刷穿 LeetCode」系列文章的第 No.297 篇，系列开始于 2021/01/01，截止于开始日 LeetCode 上共有 1916 道标题，部分是有锁题，咱们将先把所有不带锁的标题刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简练的代码。假如触及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的库房：github.com/SharingSour… 。

在库房地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更抢手的「笔试/面试」相关资料可拜访排版精美的 合集新基地