[LintCode]Serialization and Deserialization Of Binary Tree

二叉树的序列化反序列化。我是按照题目描述的BFS的方法来做的，当然还会有其他序列化的方法，不过在这里只讨论BFS的方法。BFS序列化的表示方法是，按照一层一层的顺序在string尾巴上加字符，null的话用#表示，扫到最后一层为止，也就是说最后一层的地下的null不会出现最后序列化的结果当中。

方法就是BFS的变种，BFS的时候把null也加入list中，那么这个时候就要设定一个变量来判断是不是到了最后一层。反序列的化的时候也是用BFS，注意反序列化的时候最好先按照","spliit成string数组，否则处理字符串的时候不方便处理。值得一提的是BFS用一个list就可以了，比起之前用两个代码会简洁很多。

代码如下：

	/**
	* Definition of TreeNode:
	* public class TreeNode {
	* public int val;
	* public TreeNode left, right;
	* public TreeNode(int val) {
	* this.val = val;
	* this.left = this.right = null;
	* }
	* }
	*/
	class Solution {
	private boolean isLeaf(TreeNode node) {
	return node.left == null && node.right == null;
	}
	/**
	* This method will be invoked first, you should design your own algorithm
	* to serialize a binary tree which denote by a root node to a string which
	* can be easily deserialized by your own "deserialize" method later.
	*/
	public String serialize(TreeNode root) {
	if (root == null)
	return "#";
	String res = "";
	LinkedList<TreeNode> parents = new LinkedList<TreeNode>();
	parents.add(root);
	boolean end = false;
	while (!end) {
	end = true;
	int size = parents.size();
	for (int i = 0; i < size; i++) {
	TreeNode temp = parents.removeFirst();
	String s = temp == null? "#": temp.val + "";
	res = res.length() == 0? res + s: res + "," + s;
	if (temp != null) {
	if (!isLeaf(temp))
	end = false;
	parents.add(temp.left);
	parents.add(temp.right);
	}
	}
	}
	return res;
	}
	/**
	* This method will be invoked second, the argument data is what exactly
	* you serialized at method "serialize", that means the data is not given by
	* system, it's given by your own serialize method. So the format of data is
	* designed by yourself, and deserialize it here as you serialize it in
	* "serialize" method.
	*/
	public TreeNode deserialize(String data) {
	if (data == null)
	return null;
	if (data.length() == 0)
	return null;
	if (data.equals("#"))
	return null;
	String[] strs = data.split(",");
	int len = strs.length;
	TreeNode root = new TreeNode(Integer.parseInt(strs[0]));
	LinkedList<TreeNode> parents = new LinkedList<TreeNode>();
	parents.add(root);
	int i = 1;
	while (i < len) {
	int size = parents.size();
	for (int j = 0; j < size; j++) {
	TreeNode temp = parents.removeFirst();
	temp.left = strs[i].equals("#")? null: new TreeNode(Integer.parseInt(strs[i]));
	i++;
	temp.right = strs[i].equals("#")? null: new TreeNode(Integer.parseInt(strs[i]));
	i++;
	if (temp.left != null)
	parents.add(temp.left);
	if (temp.right != null)
	parents.add(temp.right);
	}
	}
	return root;
	}
	}

view raw BST serialize.java hosted with ❤ by GitHub