題目

請設(shè)計一個算法將二叉樹序列化成一個字符串，并能將該字符串反序列化出原來二叉樹的算法。

分析

先考慮如何將二叉樹序列化為一個字符串。需要逐個遍歷二叉樹的每個節(jié)點，每遍歷到一個節(jié)點就將節(jié)點的值序列化到字符串中。以前序遍歷的順序遍歷二叉樹最適合序列化。如果采用前序遍歷的順序，那么二叉樹的根節(jié)點最先序列化到字符串中，然后是左子樹，最后是右子樹。這樣做的好處是在反序列化時最方便，從字符串中讀出的第1個數(shù)值一定是根節(jié)點的值。

實際上，只把節(jié)點的值序列化到字符串中是不夠的。首先，要用一個分隔符（如逗號）把不同的節(jié)點分隔開。其次，還要考慮如何才能在反序列化的時候構(gòu)建不同結(jié)構(gòu)的二叉樹。

盡管null節(jié)點通常沒有在圖上畫出來，但它們對樹的結(jié)構(gòu)是至關(guān)重要的。因此，應該把null節(jié)點序列化成一個特殊的字符串。如果把null節(jié)點序列化成"＃“，那么圖8.3（a）中的二叉樹用前序遍歷將被序列化成字符串"6，6，6，＃，＃，6，＃，＃，6，＃，＃”，而圖8.3（b）中的二叉樹將被序列化成字符串"6，6，＃，＃，6，6，＃，＃，6，＃，＃"。

解

public class Test {public static void main(String[] args) {TreeNode node6 = new TreeNode(6);TreeNode node66 = new TreeNode(6);TreeNode node666 = new TreeNode(6);TreeNode node6666 = new TreeNode(6);TreeNode node66666 = new TreeNode(6);node6.left = node66;node6.right = node666;node66.left = node6666;node66.right = node66666;String result = serialize(node6);System.out.println(result);TreeNode deserialize = deserialize(result);System.out.println(deserialize);}public static String serialize(TreeNode root) {if (root == null) {return "#";}String leftStr = serialize(root.left);String rightStr = serialize(root.right);return root.val + "," + leftStr + "," + rightStr;}public static TreeNode deserialize(String data) {String[] nodeStrs = data.split(",");int[] array = {0};return dfs(nodeStrs, array);}private static TreeNode dfs(String[] strs, int[] array) {String str = strs[array[0]];array[0]++;if (str.equals("#")) {return null;}TreeNode node = new TreeNode(Integer.valueOf(str));node.left = dfs(strs, array);node.right = dfs(strs, array);return node;}
}