关于后端:面试高频题难度-155一道全旧的普通面试题

题目形容

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

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

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

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

提醒: 输入输出格局与 LeetCode 目前应用的形式统一，详情请参阅 LeetCode 序列化二叉树的格局。你并非必须采取这种形式，你也能够采纳其余的办法解决这个问题。

示例 1：

输出：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, 10^4]$ 内
• $-1000 <= Node.val <= 1000$

基本思路

无论应用何种「遍历形式」进行二叉树存储，为了不便，咱们都须要对空节点有所示意。

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

层序遍历

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

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

1. 起始时，将 root 节点入队；

2. 从队列中取出节点，查看节点是否有左 / 右节点：

   • 如果有的话，将值追加序列化字符中（留神应用分隔符），并将节点入队；
   • 如果没有，查看以后节点是否为 emptyNode 节点，如果不是 emptyNode 阐明是惯例的叶子节点，须要将其对应的空节点进行存储，行将 emptyNode 入队；
3. 循环流程 $2$，直到整个队列为空。

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

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

代码：

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)$

最初

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

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

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSource/LogicStack-LeetCode。

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

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布