61、序列化二叉树

题⽬描述

请实现两个函数，分别⽤来序列化和反序列化⼆叉树
⼆叉树的序列化是指：把⼀棵⼆叉树按照某种遍历⽅式的结果以某种格式保存为字符串，从⽽使得内存中建⽴起来的⼆叉树可以持久保存。序列化可以基于先序、中序、后序、层序的⼆叉树遍历⽅式来进⾏修改，序列化的结果是⼀个字符串，序列化时通过 某种符号表示空节点（ # ），以 ！ 表示⼀个结点值的结束（ value! ）。

⼆叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str ，重构⼆叉树。例如，我们可以把⼀个只有根节点为1的⼆叉树序列化为" 1"，然后通过⾃⼰的函数来解析回这个⼆叉树

示例1
输⼊：{8,6,10,5,7,9,11}
返回值：{8,6,10,5,7,9,11}

思路及解答

序列化：使调⽤前序遍历，也就是先遍历根节点，然后再遍历左左节点，右节点，使⽤递归即可。如果为空，则⽤“ # ”代替，两者之间使⽤“ ， ”分割。

反序列化：按照逗号“ ， ”分割，使⽤index作为索引标识，每次+1 ，同样使⽤递归，先是根节点，再到左节点，再到右节点。

public class Solution {
	int index = -1;
	
	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();
	}
	
	TreeNode Deserialize(String str) {
		index++;
		String[] strs = str.split(",");
		TreeNode node = null;
		
		if(!strs[index].equals("#")) {
			node = new TreeNode(Integer.valueOf(strs[index]));
			node.left = Deserialize(str);
			node.right = Deserialize((str));
		}
		return node;
	}
}