題目

請實現兩個函數，分別用來序列化和反序列化二叉樹。

分析

我們清楚可以通過前序遍歷序列和中序遍歷序列創造出一棵二叉樹。因此，我們可以先把一棵二叉樹序列化成一個前序遍歷序列和一個中序遍歷序列，然后在反序列化時通過這兩種序列還原二叉樹。

但是，該方法有兩個缺點：

1. 該方法要求二叉樹中不能有數值重復的節點
2. 只有當兩個序列中所有數據讀出來才能開始序列化。如果兩個遍歷序列的數據是從一個流里讀出來的，那么可能需要等待較長時間。

---

實際上，如果二叉樹的序列化是從根節點開始的，那么相應的反序列化在根節點的數值讀出來的時候就可以開始了。因此，我們可以根據前序遍歷的順序來序列化二叉樹，因為前序遍歷是從根節點開始的。在遍歷二叉樹碰到空指針時，這些空指針序列化為一個特殊的字符(如$)。另外，節點的數值之間要用一個特殊字符 (如,) 隔開。

反序列化二叉樹也按照前序遍歷思路。

放碼

import com.lun.util.BinaryTree.TreeNode;public class SerializeBinaryTree {public void serialize(TreeNode node, StringBuilder result) {if(node == null) {result.append("$,");return;}result.append(node.val + ",");serialize(node.left, result);serialize(node.right, result);}public TreeNode deserialize(StringBuilder sb) {Integer number = readNum(sb);TreeNode node = null;if(number != null) {node = new TreeNode(number);node.left = deserialize(sb);node.right = deserialize(sb);}return node;}public Integer readNum(StringBuilder sb) {int firstCommaIndex = sb.indexOf(",");String numStr = sb.substring(0, firstCommaIndex);Integer result = null;if(!numStr.equals("$")) {result = Integer.valueOf(numStr);}try {sb.delete(0, firstCommaIndex + 1);}catch (Exception e) {// do nothing}return result;}}

測試

import static org.junit.Assert.*;import org.junit.Test;import com.lun.util.BinaryTree;
import com.lun.util.BinaryTree.TreeNode;public class SerializeBinaryTreeTest {@Testpublic void testSerialize() {SerializeBinaryTree sbt = new SerializeBinaryTree();StringBuilder result = new StringBuilder("");TreeNode root = makeATree();sbt.serialize(root, result);assertEquals("1,2,4,$,$,$,3,5,$,$,6,$,$,", result.toString());}@Testpublic void testReadNum() {SerializeBinaryTree sbt = new SerializeBinaryTree();StringBuilder sb = new StringBuilder("1,2,4,$,$,$,3,5,$,$,6,$,$,");assertEquals(1, sbt.readNum(sb).intValue());assertEquals("2,4,$,$,$,3,5,$,$,6,$,$,", sb.toString());assertEquals(2, sbt.readNum(sb).intValue());assertEquals("4,$,$,$,3,5,$,$,6,$,$,", sb.toString());assertEquals(4, sbt.readNum(sb).intValue());assertEquals("$,$,$,3,5,$,$,6,$,$,", sb.toString());assertNull(sbt.readNum(sb));assertEquals("$,$,3,5,$,$,6,$,$,", sb.toString());assertNull(sbt.readNum(sb));assertEquals("$,3,5,$,$,6,$,$,", sb.toString());assertNull(sbt.readNum(sb));assertEquals("3,5,$,$,6,$,$,", sb.toString());assertEquals(3, sbt.readNum(sb).intValue());assertEquals("5,$,$,6,$,$,", sb.toString());assertEquals(5, sbt.readNum(sb).intValue());assertEquals("$,$,6,$,$,", sb.toString());assertNull(sbt.readNum(sb));assertEquals("$,6,$,$,", sb.toString());assertNull(sbt.readNum(sb));assertEquals("6,$,$,", sb.toString());assertEquals(6, sbt.readNum(sb).intValue());assertEquals("$,$,", sb.toString());assertNull(sbt.readNum(sb));assertEquals("$,", sb.toString());assertNull(sbt.readNum(sb));assertEquals("", sb.toString());}@Testpublic void testDeserialize() {SerializeBinaryTree sbt = new SerializeBinaryTree();TreeNode root = null;TreeNode root2 = makeATree();StringBuilder sb = new StringBuilder("");sbt.serialize(root2, sb);root = sbt.deserialize(sb);assertTrue(BinaryTree.equals(root, root2));}private TreeNode makeATree() {TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);root.left.left = new TreeNode(4);root.right.left = new TreeNode(5);root.right.right = new TreeNode(6);return root;}}