【劍指offer】面試題37：序列化二叉樹

題目：請實作兩個函數，分别用來序列化和反序列化二叉樹。

 如果二叉樹的序列化是從根節點開始的，那麼相應的反序列化在根節點的數值讀出來的時候就可以開始了。是以，我們根據前序周遊的順序來序列化二叉樹，因為前序周遊是從根節點開始的。在周遊二叉樹碰到 null 指針時，這些 null 指針序列化成為一個特殊的字元（如“#”）。

序列化和反序列化的過程都是将二叉樹分解為 3 部分：根節點、左子樹和右子樹。我們在處理（序列化和反序列化）它的根節點之後再分别處理它的左、右子樹。這就是典型的把問題遞歸分解然後逐個解決的過程。

/**
 * 請實作兩個函數，分别用來序列化和反序列化二叉樹
 */
public class SerializeAndDeserialize {

	public class TreeNode{
		int val = 0;
		TreeNode left = null;
		TreeNode right = null;
	
		public TreeNode(int val){
			this.val = val;
		}
	}
	
	int index = -1;   // 計數變量
	
	// 将樹序列化成字元串
	public String serialize(TreeNode root){
		StringBuilder sb = new StringBuilder();
		
		if(root == null){
			sb.append("#,");
			return sb.toString();
		}
		
		sb.append(root.val + ",");
		sb.append(serialize(root.left));
		sb.append(serialize(root.right));
		
		return sb.toString();
	} 
	
	// 将字元串反序列化成樹
	public TreeNode deserialize(String str){
		index++;
		String[] string = str.split(",");
		TreeNode node = null;
		if(!string[index].equals("#")){
			node = new TreeNode(Integer.valueOf(string[index]));
			node.left = deserialize(str);
			node.right = deserialize(str);
		}
		return node;
	}
}