二叉树的序列化和反序列化
作者：Grey
原文地址：
题目链接见：LeetCode 297. Serialize and Deserialize Binary Tree
主要思路
可以用如下三种方式
第一种方式，先序遍历生成序列化字符串，然后按先序规则再反序列化；
第二种方式，后序遍历生成序列化字符串，然后按后序规则再反序列化；
第三种方式，按层遍历生成序列化字符串，然后按层次规则再反序列化。
注：这里不能用中序方式序列化和反序列化，因为，如果二叉树是如下两棵
两棵树的中序遍历结果都是[null,a,a,a,null]，这样进行反序列化的时候，就无法区分这两棵树了。
其次，针对任何一棵二叉树，我们需要将一些空的节点补充完整，比如下述二叉树
其中 b 的左孩子，c 的左孩子，d 的右孩子，都是空节点，我们可以用 null 来表示，但是不能忽略，所以以按层序列化为例，我们将空节点设置为‘#’字符，并用'[]'框住序列化的字符串，然后用逗号分隔节点，所以，上述二叉树
按层序列化的结果是[a,b,c,#,d,#,e,f,#]
代码如下
// 二叉树按层遍历经典实现。 public static String serialize(TreeNode head) { if (head == null) { return "[]"; } StringBuilder sb = new StringBuilder("["); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(head); while (!queue.isEmpty()) { TreeNode node = queue.poll(); sb.append(node == null ? "#" : String.valueOf(node.val)).append(","); if (node != null) { queue.offer(node.left); queue.offer(node.right); } } sb.append("]"); return sb.toString(); } 反序列化的方式就是把上述字符串还原成一个二叉树，使用一个队列即可，代码如下：
// 按层反序列化 public static TreeNode deserialize(String data) { if ("[]".equals(data)) { return null; } data = data.substring(1, data.length() - 2); String[] values = data.split(","); TreeNode head = new TreeNode(Integer.valueOf(values[0])); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(head); int size = 1; while (!queue.isEmpty() && size < values.length) { TreeNode c = queue.poll(); c.left = "#".equals(values[size]) ? null : new TreeNode(Integer.valueOf(values[size])); size++; if (size < values.length) { c.right = "#".equals(values[size]) ? null : new TreeNode(Integer.valueOf(values[size])); size++; } if (c.left != null) { queue.offer(c.left); } if (c.right != null) { queue.offer(c.right); } } return head; } 先序序列化/反序列化，后序序列化/反序列化方法类似
// 后序方式序列化 迭代方法 public static String serialize3(TreeNode head) { if (head == null) { return "[]"; } // 后序遍历的结果加入栈（可以用递归也可以用迭代） Stack<TreeNode> stack1 = new Stack<>(); Stack<TreeNode> stack2 = new Stack<>(); stack1.push(head); while (!stack1.isEmpty()) { TreeNode c = stack1.pop(); stack2.push(c); if (c != null) { stack1.push(c.left); stack1.push(c.right); } } // 栈->字符串 StringBuilder sb = new StringBuilder("["); while (!stack2.isEmpty()) { TreeNode node = stack2.pop(); sb.append(node == null ? "#" : node.val).append(","); } sb.append("]"); return sb.toString(); } // 后序方式反序列化 迭代方式 public static TreeNode deserialize3(String data) { if ("[]".equals(data)) { return null; } String[] values = data.substring(1, data.length() - 2).split(","); Stack<String> stack = new Stack<>(); for (String value : values) { stack.push(value); } return posDerial(stack); } private static TreeNode posDerial(Stack<String> stack) { String s = stack.pop(); if ("#".equals(s)) { return null; } TreeNode root = new TreeNode(Integer.valueOf(s)); root.right = posDerial(stack); root.left = posDerial(stack); return root; } // 先序方式序列化 迭代做法 // 头 左 右 public static String serialize2(TreeNode head) { if (head == null) { return "[]"; } StringBuilder sb = new StringBuilder("["); Stack<TreeNode> queue = new Stack<>(); queue.push(head); while (!queue.isEmpty()) { TreeNode c = queue.pop(); sb.append(c == null ? "#" : c.val).append(","); if (c != null) { queue.push(c.right); queue.push(c.left); } } sb.append("]"); return sb.toString(); } // 先序反序列化 public static TreeNode deserialize2(String data) { if ("[]".equals(data)) { return null; } String[] values = data.substring(1, data.length() - 2).split(","); Queue<TreeNode> queue = new LinkedList<>(); for (String value : values) { queue.offer("#".equals(value) ? null : new TreeNode(Integer.valueOf(value))); } return preDesrial(queue); } private static TreeNode preDesrial(Queue<TreeNode> queue) { TreeNode node = queue.poll(); if (node == null) { return null; } node.left = preDesrial(queue); node.right = preDesrial(queue); return node; } 
