297. Serialize and Deserialize Binary Tree

Apparently, we need a queue to implement bfs algorithm. The key of serializing and deserizalizing binary tree through bfs is simulating child nodes of all leaf nodes.

• During serialization, we use # to denote the left node and right node of leaf nodes. After simulation, each node besides leaf node (simulated node denoted by #) will have two child nodes in the tree. And the value of each node is separated through a self-defined special character X. (Of course, we can use other characters)
• During deserialization, we build binary tree level by level. At each level, we use a variable nonNull to count the number of non null node in current level. Because of our simulation operation during serialization, the number of nodes in next level is twice the number of non null nodes in current level.

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder("");
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);
    while( !queue.isEmpty() ) {
	TreeNode peekNode = queue.poll();
	if( peekNode == null )
	    sb.append("#X");
	else{ 
	    sb.append(peekNode.val + "X");
	    queue.offer(peekNode.left);
	    queue.offer(peekNode.right);
	}
    }
    return sb.toString();
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    String valueArray[] = data.split("X");
    TreeNode nodeArray[] = new TreeNode[valueArray.length];
    for(int i = 0; i < valueArray.length; i++) 
	if( !valueArray[i].equals("#") )
	    nodeArray[i] = new TreeNode(Integer.parseInt(valueArray[i]));
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(nodeArray[0]);
    int size = queue.size(), index = 1;
    while( !queue.isEmpty() ) { 
	int nonNull = 0; // count the non null node of current level
	for(int i = 0; i < size; i++) { // build the tree level by level
	    TreeNode peekNode = queue.poll();
	    if( peekNode != null ) {
		nonNull++;
		peekNode.left = nodeArray[index];
		queue.offer(nodeArray[index++]);
		peekNode.right = nodeArray[index];
		queue.offer(nodeArray[index++]);
	    }
	}
	size = nonNull * 2; // get the number of node in next level
    }
    return nodeArray[0];
}