备案的时候网站要建设好吗/企业推广网站有哪些

题目

二叉树被记录成文件的过程叫作二叉树的序列化，通过文件内容重建原来二叉树的过程叫作反序列化。给定一颗二叉树的头节点head，并已知二叉树节点值为32bit整型。请设计一种二叉树序列化和反序列化的方案。

难度：💗

设计

概要设计

一个二叉树图概貌

digraph {

1->2;

1->3;

2->null;

2->null;

3->null;

3->null;

}

二叉树的初始原型

class Node{

int value;

Node left;

Node right;

public Node(int value){

this.value = value;

}

}

序列号符号 # 表示 null ，! 表示节点值的结束 ，不用标识符对产生的结果不好分辨

能用循环完成操作且理解难度不大的情况下能不用递归就不用递归，效率太低

详细设计

序列化

如果节点为空，返回 #! ，表示为空且已结束

一个接收节点结束值的字符串，String resultString = node.value + "!"

一个存储节点结构，相比之下队列比栈、集合、数组等要符合层遍历的原则

判断队列存储的节点是否为空，如果为空直接返回resultString，不为空继续进行

将队列第一的存储(节点)，用 poll() 删除，并再次放入源节点中

如果左分支为null，返回 #!，反之则将节点的左分支累加在接收字符串变量上

右分支同理

实现

序列化的实现

String nodeSerialToString(Node node){

if (node == null){

return "#!";

}

String resultString = node.value + "!";

Queue queue = new LinkedList<>();

queue.offer(node);

while(!queue.isEmpty()){

node = queue.poll();

if (node.left != null){

resultString += node.left.value + "!";

queue.offer(node.left);

}else {

resultString += "#!";

}

if (node.right != null){

resultString += node.right.value + "!";

queue.offer(node.right);

}else {

resultString += "#!";

}

}

return resultString;

}

详细设计

反序列化

首先将字符串结束符! 进行分割，装入数组中

null 的标识符 # 替换成 null

将处理完成(类型值替换)的数组值，加入新节点并返回

用队列存储节点，初始化一个空节点

如果头节点为空直接返回头节点，反之则将头节点放入队列中

如果队列不为空，则将用 poll() 赋值到初始节点上

再将处理完成的数组(类型值替换)，重新赋值到节点的左右分支上

返回头节点，因为节点类型是一致的，所以可以像head.left.left 层层调用

实现

反序列化

/** 反序列化 */

Node serialStringToNode(String str){

String strings[] = str.split("!");

int ndx = 0;

Node head = generateNodeByString(strings[ndx]);

Queue queue = new LinkedList<>();

queue.offer(head);

while (!queue.isEmpty()){

Node node = queue.poll();

ndx++;

node.left = generateNodeByString(strings[ndx]);

ndx++;

node.right = generateNodeByString(strings[ndx]);

if (node.left != null){

queue.offer(node.left);

}

if (node.right != null){

queue.offer(node.right);

}

}

return head;

}

/** 将字符串值转成数值并生成新的节点值 */

Node generateNodeByString(String str){

String nulTag = "#";

if (nulTag.equals(str)){

return null;

}

return new Node(Integer.parseInt(str));

}

校验功能测试