題目

請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法將二叉樹序列化成一個(gè)字符串，并能將該字符串反序列化出原來二叉樹的算法。

分析

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

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

盡管null節(jié)點(diǎn)通常沒有在圖上畫出來，但它們對(duì)樹的結(jié)構(gòu)是至關(guān)重要的。因此，應(yīng)該把null節(jié)點(diǎn)序列化成一個(gè)特殊的字符串。如果把null節(jié)點(diǎn)序列化成"＃“，那么圖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;}
}