二叉树的序列化和反序列化
引言
结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
题目
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
示例 ：
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
提示：
- 树中结点数在范围
[0, 104]内 -1000 <= Node.val <= 1000
前序遍历解法
前序遍历框架:
void traverse(TreeNode root) {
if (root == null) return;
// 前序遍历的代码
traverse(root.left);
traverse(root.right);
}
实现代码:
//leetcode submit region begin(Prohibit modification and deletion)
import java.util.LinkedList;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
String NULL = "#";
String SEP = ",";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serialize(root, sb);
return sb.toString();
}
void serialize(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append(NULL).append(SEP);
return;
}
sb.append(root.val).append(SEP);
serialize(root.left);
serialize(root.right);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
LinkedList<String> nodes = new LinkedList<>();
for (String s : data.split(SEP)) {
nodes.addLast(s);
}
return deserialize(nodes);
}
TreeNode deserialize(LinkedList<String> nodes) {
if (nodes.isEmpty()) {
return null;
}
String first = nodes.removeFirst();
if (first.equals(NULL)) {
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(first));
root.left = deserialize(nodes);
root.right = deserialize(nodes);
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
//leetcode submit region end(Prohibit modification and deletion)
测试
20:42 info
运行成功:
测试用例:[1,2,3,null,null,4,5]
测试结果:[1]
期望结果:[1,2,3,null,null,4,5]
stdout:
后序遍历解法
二叉树的后续遍历框架：
void traverse(TreeNode root) {
if (root == null) return;
traverse(root.left);
traverse(root.right);
// 后序遍历的代码
}
实现代码:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
String SEP = ",";
String NULL = "#";
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serialize(root, sb);
return sb.toString();
}
void serialize(TreeNode root, StringBuilder sb) {
// base case
if (root == null) {
sb.append(NULL).append(SEP);
return;
}
serialize(root.left, sb);
serialize(root.right, sb);
// 后续遍历
sb.append(root.val).append(SEP);
}
public TreeNode deserialize(String data) {
LinkedList<String> nodes = new LinkedList<>();
for (String s : data.split(SEP)) {
nodes.addLast(s);
}
return deserialize(nodes);
}
TreeNode deserialize(LinkedList<String> nodes) {
if (nodes.isEmpty()) {
return null;
}
// 后续遍历:
String last = nodes.removeLast();
if (last.equals(NULL)) {
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(last));
root.right = deserialize(nodes);
root.left = deserialize(nodes);
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
中序遍历解法
先说结论，中序遍历的方式行不通，因为无法实现反序列化方法 deserialize。
要想实现反序列方法，首先要构造 root 节点。前序遍历得到的 nodes 列表中，第一个元素是 root 节点的值；后序遍历得到的 nodes 列表中，最后一个元素是 root 节点的值。
你看上面这段中序遍历的代码，root 的值被夹在两棵子树的中间，也就是在 nodes 列表的中间，我们不知道确切的索引位置，所以无法找到 root 节点，也就无法进行反序列化。
层次遍历解法
层次遍历二叉树的代码框架：
void traverse(TreeNode root) {
if (root == null) return;
// 初始化队列，将 root 加入队列
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
TreeNode cur = q.poll();
/* 层级遍历代码位置 */
System.out.println(root.val);
/*****************/
if (cur.left != null) {
q.offer(cur.left);
}
if (cur.right != null) {
q.offer(cur.right);
}
}
}
实现代码:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Codec {
String SEP = ",";
String NULL = "#";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) { return ""; }
StringBuilder sb = new StringBuilder();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
// 层次遍历
if (node == null) {
sb.append(NULL).append(SEP);
continue;
}
sb.append(node.val).append(SEP);
queue.offer(node.left);
queue.offer(node.right);
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.isEmpty()) { return null; }
String[] nodes = data.split(SEP);
TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
for (int i = 1; i < nodes.length; ) {
TreeNode parent = queue.poll();
String left = nodes[i++];
if (!left.equals(NULL)) {
parent.left = new TreeNode(Integer.parseInt(left));
queue.offer(parent.left);
} else {
parent.left = null;
}
String right = nodes[i++];
if (!right.equals(NULL)) {
parent.right = new TreeNode(Integer.parseInt(right));
queue.offer(parent.right);
} else {
parent.right = null;
}
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 jungle8884@163.com
