十六.二叉树的序列化和反序列化

【题目】

二叉树的序列化和反序列化

【定义】

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

【思路】

一.先序遍历二叉树序列化（递归）

1.中间结点的值加入到字符串中

2.左边节点的值加入到字符串中（递归）（左边节点作为左子树的中间结点，加入顺序是中左右，是递归）

3.右边节点的值加入到字符串中（递归）（右边节点作为右子树的中间结点，加入顺序是中左右，是递归）

二.层级遍历二叉树序列化（需要一个队列保存住左右顺序）

1.中间结点的值加入到字符串中

2.建立一个队列，把中间结点加进去

3.队列不为空的时候，弹出一个（表示当前操作的是这个节点），如果他的左不为空，构建字符串，加入到队列（为了保证下一个操作的是第二层左节点），如果他的右不为空，构建字符串，加入到队列（操作的是第二层右节点），结束条件是队列中没有节点了，表示所有的节点都操作完了。

三.先序遍历二叉树反序列化（递归）

1.字符串拆分为字符串数组，

2.建立一个队列保存住这个字符串数组（因为涉及到里面节点的操作，需要弹出，同时还要保证先后顺序）

3.弹出元素，不为空的话说明是一个结点，第一个弹出的是头结点，建立左子树（弹出来的是头结点的左子树上），建立右子树（递归调用）

四.层级遍历二叉树反序列化

1.字符串拆分为字符串数组，

2.建立好第一个节点，加入到队列中；

3.如果当前队列不为空，弹出一个，构建好他的左右节点；压入栈，下一个操作的是左节点。

【序列化代码实现】

//中左右(先序遍历序列化)
	public static String serialByPre(Node head) {
		if (head==null) {
			return "#_";
		}
		String res=head.value+"_";
		res+=serialByPre(head.left);
		res+=res+serialByPre(head.right);
		return res;
		}
	
	//层级遍历序列化
	public static String serialByLevel(Node head) {
		if (head==null) {
			return "#_";
		}
		String res=head.value+"_";
		Queue<Node> queue=new LinkedList<>();
		queue.offer(head);
		while(!queue.isEmpty()) {
		head=queue.poll();//弹出队列的第一个元素就是头结点，第二次是头结点的左，第三次是头结点的右
			if(head.left!=null) {
				res+=head.left.value+"_";
				queue.offer(head.left);//队列尾部插入元素
			}else {
				res+="#_";
			}
			if(head.right!=null) {
				res+=head.right.value+"_";
				queue.offer(head.right);
			}else {
				res+="#_";
			}
		}
		return res;		
	}
           

【反序列化代码实现】

//先序遍历反序列化
//1.根据_拆分为字符串数组,存到一个队列中
public static Node reconByPreString(String res) {
		String[] values=res.split("_");
		Queue<String> queue=new LinkedList<>();
		for (int i = 0; i < values.length; i++) {
			queue.offer(values[i]);
		}
		return reconPreOrder(queue);
	}
//2.构造二叉树
	public  static Node reconPreOrder(Queue<String> queue) {
		String value=queue.poll();
		if (value.equals("#")) {
			return null;
		}
		Node head=new Node(Integer.valueOf(value));//队列中第一个弹出来的是还原头结点
		head.left=reconPreOrder(queue);//去掉头结点后下一个就是左子树的头结点（递归调用）
		head.right=reconPreOrder(queue);//去掉左边的头结点后，就是右子树的头结点（递归调用）
		return head;	
	}
           

//层级遍历反序列化
	public static Node reconByLevelString(String res) {
		String[] values=res.split("_");
		int index=0;
		Node head=generateNodeByString(values[index++]);//头结点生成了
		Queue<Node> queue=new LinkedList<>();
		if (head!=null) {
			queue.offer(head);//头结点压入栈
		}
		Node node=null;
		if(!queue.isEmpty()) {
			node=queue.poll();//栈不为空，弹出来的是头结点
			node.left=generateNodeByString(values[index++]);//头结点的左构造成功
			node.right=generateNodeByString(values[index++]);//头结点的右构造成功
			//左右节点都存在的话，都压入队列中，使队列不为空，在弹出来的就是头结点的左节点，构造他的左右，第三次弹出来的是头结点的右节点，构造他的左右
			if (node.left!=null) {
				queue.offer(node.left);
			}
			if (node.right!=null) {
				queue.offer(node.right);
			}
		}
		return head;
	}


	public static Node generateNodeByString(String val) {
		if(val.equals("#")) {
			return null;
		}
		return new Node(Integer.valueOf(val));
	}