当前位置:网站首页>二叉树的序列化和反序列化
二叉树的序列化和反序列化
2022-08-09 12:00:00 【爱敲代码的Harrison】
- 可以用先序或者中序或者后序或者按层遍历,来实现二叉树的序列化
- 用了什么方式序列化,就用什么样的方式反序列化
- 但是,二叉树无法通过中序遍历的方式实现序列化和反序列化
- 所以,二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化,
- 不同的两棵树,可能得到同样的中序序列,即便补了空位置也可能一样。比如如下两棵树,补足空位置的中序遍历结果都是{ null, 1, null, 2, null}
// __2
// /
// 1
// 和
// 1__
// \
// 2
package com.harrison.class07;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/** * @author Harrison * @create 2022-03-09-14:58 * @motto 众里寻他千百度,蓦然回首,那人却在灯火阑珊处。 */
public class Code04_SerializeAndReconstructBT {
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int v){
value=v;
}
}
// 先序序列化
public static Queue<String> preSerial(Node head){
Queue<String> ans=new LinkedList<>();
pres(head,ans);
return ans;
}
public static void pres(Node head,Queue<String> ans){
if(head==null){
ans.add(null);
}else{
ans.add(String.valueOf(head.value));
pres(head.left,ans);
pres(head.right,ans);
}
}
// 先序重建
public static Node buildByPreQueue(Queue<String> preList){
if(preList==null || preList.size()==0){
return null;
}
return preb(preList);
}
public static Node preb(Queue<String> preList){
String value=preList.poll();
if(value==null){
return null;
}
Node head=new Node(Integer.valueOf(value));
head.left=preb(preList);
head.right=preb(preList);
return head;
}
// 后序序列化
public static Queue<String> posSerial(Node head){
Queue<String> ans=new LinkedList<>();
poss(head,ans);
return ans;
}
public static void poss(Node head,Queue<String> ans){
if(head==null){
ans.add(null);
}else{
poss(head.left,ans);
poss(head.right,ans);
ans.add(String.valueOf(head.value));
}
}
// 后序重建 左右根 -》 根右左
public static Node buildByPosQueue(Queue<String> posList){
if(posList==null || posList.size()==0){
return null;
}
Stack<String> stack=new Stack<>();
while(!posList.isEmpty()){
stack.push(posList.poll());
}
return posb(stack);
}
public static Node posb(Stack<String> posStack){
String value=posStack.pop();
if(value==null){
return null;
}
Node head=new Node(Integer.valueOf(value));
head.right=posb(posStack);
head.left=posb(posStack);
return head;
}
// 按层序列化
public static Queue<String> levelSerial(Node head){
Queue<String> ans=new LinkedList<>();
if(head==null){
ans.add(null);
}else{
ans.add(String.valueOf(head.value));
Queue<Node> queue=new LinkedList<>();
queue.add(head);
while(!queue.isEmpty()){
head=queue.poll();
if(head.left!=null){
ans.add(String.valueOf(head.left.value));
queue.add(head.left);
}else{
ans.add(null);
}
if(head.right!=null){
ans.add(String.valueOf(head.right.value));
queue.add(head.right);
}else{
ans.add(null);
}
}
}
return ans;
}
// 按层重建
public static Node buildByLevelQueue(Queue<String> levelList){
if(levelList==null || levelList.size()==0){
return null;
}
Queue<Node> queue=new LinkedList<>();
Node head=generateNode(levelList.poll());
if(head!=null){
queue.add(head);
}
Node node=null;
while(!queue.isEmpty()){
node=queue.poll();
node.left=generateNode(levelList.poll());
node.right=generateNode(levelList.poll());
if(node.left!=null){
queue.add(node.left);
}
if(node.right!=null){
queue.add(node.right);
}
}
return head;
}
public static Node generateNode(String value){
if(value==null){
return null;
}
return new Node(Integer.valueOf(value));
}
public static Node generate(int level,int maxLevel,int maxValue){
if(level>maxLevel || Math.random()<0.5){
return null;
}
Node head=new Node((int)(Math.random()*maxValue));
head.left=generate(level+1,maxLevel,maxValue);
head.right=generate(level+1,maxLevel,maxValue);
return head;
}
public static Node generateRandomBST(int maxLevel,int maxValue){
return generate(1,maxLevel,maxValue);
}
public static boolean isSameValueStructure(Node head1, Node head2) {
if (head1 == null && head2 != null) {
return false;
}
if (head1 != null && head2 == null) {
return false;
}
if (head1 == null && head2 == null) {
return true;
}
if (head1.value != head2.value) {
return false;
}
return isSameValueStructure(head1.left, head2.left) && isSameValueStructure(head1.right, head2.right);
}
public static void main(String[] args) {
int maxLevel = 5;
int maxValue = 100;
int testTimes = 1000000;
System.out.println("test begin");
for (int i = 0; i < testTimes; i++) {
Node head = generateRandomBST(maxLevel, maxValue);
Queue<String> pre = preSerial(head);
Queue<String> pos = posSerial(head);
Queue<String> level = levelSerial(head);
Node preBuild = buildByPreQueue(pre);
Node posBuild = buildByPosQueue(pos);
Node levelBuild = buildByLevelQueue(level);
if (!isSameValueStructure(preBuild, posBuild) || !isSameValueStructure(posBuild, levelBuild)) {
System.out.println("Oops!");
}
}
System.out.println("test finish!");
}
}
边栏推荐
- HAproxy:负载均衡
- 脱光衣服待着就能减肥,当真有这好事?
- Experiment record: the process of building a network
- Common gadgets of Shell (sort, uniq, tr, cut)
- 曼城推出可检测情绪的智能围巾,把球迷给整迷惑了
- Information system project managers must memorize the core test sites (63) The main process of project portfolio management & DIPP analysis
- 张朝阳对话俞敏洪:一边是手推物理公式,一边是古诗信手拈来
- 字符串 | 反转字符串 | 双指针法 | leecode刷题笔记
- ACM longest non-descent subsequence problem
- 智驾科技完成C1轮融资,此前2轮已融4.5亿元
猜你喜欢
JD.com architects tidy up: what are the core technical knowledge points of jvm and performance tuning
00后写个暑假作业,被监控成这笔样
LeetCode热题(11.合并两个有序链表)
redis库没法引入
【面试高频题】可逐步优化的链表高频题
张朝阳对话俞敏洪:一边是手推物理公式,一边是古诗信手拈来
太卷了... 腾讯一面被问到内存满了,会发生什么?
AI篮球裁判火了,走步算得特别准,就问哈登慌不慌
The batch size does not have to be a power of 2!The latest conclusions of senior ML scholars
2022 Niu Ke Duo School (6) M. Z-Game on grid
随机推荐
ACM01 Backpack problem
2022牛客多校(六)M. Z-Game on grid
Gumbel_Softmax 概要
Programmer's Exclusive Romance - Use 3D Engine to Realize Fireworks in 5 Minutes
proto3-2 syntax
荣耀携手Blue Yonder,加快企业战略增长
内网穿透工具ngrok使用教程
LeetCode #101. 对称二叉树
PM2之配置文件
CANopen DS402名词
Shell之常用小工具(sort、uniq、tr、cut)
WeChat side: what is consistent hashing, usage scenarios, and what problems does it solve?
基于STM32+铂电阻设计的测温仪
从零开始Blazor Server(9)--修改Layout
信息系统项目管理师必背核心考点(六十三)项目组合管理的主要过程&DIPP分析
ACM longest non-descent subsequence problem
Summary of learning stages (knapsack problem)
Recommend a free 50-hour AI computing platform
electron 应用开发优秀实践
无需精子卵子子宫体外培育胚胎,Cell论文作者这番话让网友们炸了