左神算法：二叉树的序列化和反序列化（Java版）

本文主要是介绍左神算法：二叉树的序列化和反序列化（Java版），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本题来自左神《程序员代码面试指南》“二叉树的序列化和反序列化”题目。

题目

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

题解

本文提供两套序列化和反序列化的实现，供读者参考。

方法一：通过先序遍历实现序列化和反序列化。

先介绍先序遍历下的序列化过程，首先假设序列化的结果字符串为str，初始时str=""。先序遍历二叉树，如果遇到null 节点，就在str 的末尾加上“#!”，“#”表示这个节点为空，节点值不存在，“!”表示一个值的结束；如果遇到不为空的节点，假设节点值为3，就在str 的末尾加上“3!”。比如，如图3-6 所示的二叉树。

根据上文的描述，先序遍历序列化，最后的结果字符串str 为：12!3!#!#!#!。为什么要在每个节点值的后面都要加上“!”呢？因为，如果不标记一个值的结束，那么最后产生的结果会有歧义，如图3-7 所示。
在这里插入图片描述
如果不在一个值结束时加入特殊字符，那么图3-6 和图3-7 的先序遍历序列化结果都是123###。也就是说，生成的字符串并不代表唯一的树。

先序遍历序列化的全部过程请参看如下代码中的serialByPre 方法。

	public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}public static String serialByPre(Node head) {if (head == null) {return "#!";}String res = head.value + "!";res += serialByPre(head.left);res += serialByPre(head.right);return res;}

在这里插入图片描述

public static Node reconByPreString(String preStr) {String[] values = preStr.split("!");Queue<String> queue = new LinkedList<String>();for (int i = 0; i != values.length; i++) {queue.offer(values[i]);}return reconPreOrder(queue);
}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;
}

方法二：通过层遍历实现序列化和反序列化。

先介绍层遍历下的序列化过程。首先假设序列化的结果字符串为str，初始时str=“空”。然后实现二叉树的按层遍历，具体方式是利用队列结构，这也是宽度遍历图的常见方式。例如，图3-8 所示的二叉树。
在这里插入图片描述
按层遍历图3-8 所示的二叉树，最后str="1!2!3!4!#!#!5!#!#!#!#! "。

层遍历序列化的全部过程请参看如下代码中的serialByLevel 方法。

public static String serialByLevel(Node head) {if (head == null) {return "#!";}String res = head.value + "!";Queue<Node> queue = new LinkedList<Node>();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;
}

先序遍历的反序列化其实就是重做先序遍历，遇到"#“就生成null 节点，结束生成后续子树的过程。与根据先序遍历的反序列化过程一样，根据层遍历的反序列化是重做层遍历，遇到”#"就生成null 节点，同时不把null 节点放到队列里即可。

层遍历反序列化的全部过程请参看如下代码中的 reconByLevelString 方法。

public static Node reconByLevelString(String levelStr) {String[] values = levelStr.split("!");int index = 0;Node head = generateNodeByString(values[index++]);Queue<Node> queue = new LinkedList<Node>();if (head != null) {queue.offer(head);}Node node = null;while (!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));
}

附：完整代码

package chapter_3_binarytreeproblem;import java.util.LinkedList;
import java.util.Queue;public class Problem_04_SerializeAndReconstructTree {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}public static String serialByPre(Node head) {if (head == null) {return "#!";}String res = head.value + "!";res += serialByPre(head.left);res += serialByPre(head.right);return res;}public static Node reconByPreString(String preStr) {String[] values = preStr.split("!");Queue<String> queue = new LinkedList<String>();for (int i = 0; i != values.length; i++) {queue.offer(values[i]);}return reconPreOrder(queue);}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 String serialByLevel(Node head) {if (head == null) {return "#!";}String res = head.value + "!";Queue<Node> queue = new LinkedList<Node>();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;}public static Node reconByLevelString(String levelStr) {String[] values = levelStr.split("!");int index = 0;Node head = generateNodeByString(values[index++]);Queue<Node> queue = new LinkedList<Node>();if (head != null) {queue.offer(head);}Node node = null;while (!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));}// for test -- print treepublic static void printTree(Node head) {System.out.println("Binary Tree:");printInOrder(head, 0, "H", 17);System.out.println();}public static void printInOrder(Node head, int height, String to, int len) {if (head == null) {return;}printInOrder(head.right, height + 1, "v", len);String val = to + head.value + to;int lenM = val.length();int lenL = (len - lenM) / 2;int lenR = len - lenM - lenL;val = getSpace(lenL) + val + getSpace(lenR);System.out.println(getSpace(height * len) + val);printInOrder(head.left, height + 1, "^", len);}public static String getSpace(int num) {String space = " ";StringBuffer buf = new StringBuffer("");for (int i = 0; i < num; i++) {buf.append(space);}return buf.toString();}public static void main(String[] args) {Node head = null;printTree(head);String pre = serialByPre(head);System.out.println("serialize tree by pre-order: " + pre);head = reconByPreString(pre);System.out.print("reconstruct tree by pre-order, ");printTree(head);String level = serialByLevel(head);System.out.println("serialize tree by level: " + level);head = reconByLevelString(level);System.out.print("reconstruct tree by level, ");printTree(head);System.out.println("====================================");head = new Node(1);printTree(head);pre = serialByPre(head);System.out.println("serialize tree by pre-order: " + pre);head = reconByPreString(pre);System.out.print("reconstruct tree by pre-order, ");printTree(head);level = serialByLevel(head);System.out.println("serialize tree by level: " + level);head = reconByLevelString(level);System.out.print("reconstruct tree by level, ");printTree(head);System.out.println("====================================");head = new Node(1);head.left = new Node(2);head.right = new Node(3);head.left.left = new Node(4);head.right.right = new Node(5);printTree(head);pre = serialByPre(head);System.out.println("serialize tree by pre-order: " + pre);head = reconByPreString(pre);System.out.print("reconstruct tree by pre-order, ");printTree(head);level = serialByLevel(head);System.out.println("serialize tree by level: " + level);head = reconByLevelString(level);System.out.print("reconstruct tree by level, ");printTree(head);System.out.println("====================================");head = new Node(100);head.left = new Node(21);head.left.left = new Node(37);head.right = new Node(-42);head.right.left = new Node(0);head.right.right = new Node(666);printTree(head);pre = serialByPre(head);System.out.println("serialize tree by pre-order: " + pre);head = reconByPreString(pre);System.out.print("reconstruct tree by pre-order, ");printTree(head);level = serialByLevel(head);System.out.println("serialize tree by level: " + level);head = reconByLevelString(level);System.out.print("reconstruct tree by level, ");printTree(head);System.out.println("====================================");}
}