长春免费建站,东营网站开发公司,wordpress筛选热门列表,微盟微商城怎么样本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 序列化是指将一个数据结构转化为位序列的过程因此可以将其存储在文件中或内存缓冲区中以便稍后在相同或不同的计算机环境中恢复结构。
设计一个序列化和反序列化 N N N 叉树的算法。一个 N N N 叉树是指每个节点都有不超过 N N N 个孩子节点的有根树。序列化 / 反序列化算法的算法实现没有限制。你只需要保证 N N N 叉树可以被序列化为一个字符串并且该字符串可以被反序列化成原树结构即可。
例如你需要序列化下面的 3-叉 树。 为 [1 [3[5 6] 2 4]]。你不需要以这种形式完成你可以自己创造和实现不同的方法。
或者您可以遵循 LeetCode 的层序遍历序列化格式其中每组孩子节点由空值分隔。 例如上面的树可以序列化为 [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
你不一定要遵循以上建议的格式有很多不同的格式所以请发挥创造力想出不同的方法来完成本题。
示例 1:
输入: root [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出: [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]示例 2:
输入: root [1,null,3,2,4,null,5,6]
输出: [1,null,3,2,4,null,5,6]示例 3:
输入: root []
输出: []提示
树中节点数目的范围是 [0, 10^4].0 Node.val 10^4 N N N 叉树的高度小于等于 1000不要使用类成员 / 全局变量 / 静态变量来存储状态。你的序列化和反序列化算法应是无状态的。 类似题目
449. 序列化和反序列化二叉搜索树297. 二叉树的序列化与反序列化 困难428. 序列化和反序列化 N 叉树 困难 解法 BFS类似LeetCode层序遍历格式StringJoiner
import java.util.StringJoiner;
class Codec {// Encodes a tree to a single string.public String serialize(Node root) {if (root null) return ;StringJoiner sj new StringJoiner(,);DequeNode queue new ArrayDeque();queue.offer(root);sj.add(Integer.toString(root.val));sj.add(null);while (!queue.isEmpty()) {Node curr queue.poll();for (Node node : curr.children) { // 将每个节点的子节点作为一组,由空值分隔sj.add(Integer.toString(node.val));queue.offer(node);}sj.add(null);}return sj.toString();}// Decodes your encoded data to tree.public Node deserialize(String data) {if (data.isEmpty()) return null;String[] tokens data.split(,);DequeNode queue new ArrayDeque();int index 0;Node root new Node(Integer.parseInt(tokens[index]), new ArrayListNode());index; // 跳过nullqueue.offer(root); while (!queue.isEmpty()) {Node curr queue.poll();while (index tokens.length) {if (tokens[index].equals(null)) {index;break;}Node node new Node(Integer.parseInt(tokens[index]), new ArrayListNode());curr.children.add(node);queue.offer(node);}}return root;}
}复杂度分析
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( n ) O(n) O(n)
当然也可以选择类似JSON那样有层次的序列化格式。总之序列化和反序列的题目很发散各种解法都行。
