Binary Tree Serialization

LintCode LeetCode

这道题是写Binary Tree的序列化和反序列化。测试程序不会看你序列化后的结果，只会去验证你的程序序列化后的String再反序列化，是不是原来的树。

 public class Solution{
    public String serialize(TreeNode root){
        if (root == null) {
            return "{}";        
        }
        ArrayList<TreeNode> queue = new ArrayList<>();
        queue.add(root);
        for (int i = 0; i < queue.size(); i++){
            TreeNode temp = queue.get(i);
            if (temp == null) {
                continue;
            }
            queue.add(root.left);
            queue.add(root.right);
        }
        while ( queue.get(queue.size() - 1) == null){
            queue.remove(queue.size() - 1);
        }
        StringBuilder sb = new StringBuilder;
        sb.append("{");
        for (int i = 0; i < queue.size(); i++) {
            if (queue.get(i) == null){
                sb.append(",#");
            } else {
                sb.append(",");
                sb.append(queue.get(i).val);
            }
        }
        sb.append("}");
    }
    public TreeNode deserialize(String data) {
        if (data.equals("{}")){
            return null;
        }
        String [] vals = data.substring(1,data.length - 1).split(",");
        ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        queue.add(root);
        int index = 0;
        boolean isLeftChild;
        for (int i = 1; i < vals.length; i++){
            if (!vals[i].equals("#"){
                TreeNode node = new TreeNode(Integer.parseInt(vals[i]));
                if (isLeftChild){
                    queue.get(i).left = node;
                } else {
                    queue.get(i).right = node;
                }
                queue.add(node);
            }
            if (!isLeftChild( {
                index += 1;
            }
            isLeftChild = !isLeftChild;
        }
        return root;
    }
 }

想知道deserialize的时候，那个queue有什么用？
在群里问了一下为什么这道题看起来不像宽搜的模版，宽搜的模版不是都有

while (!queue.isEmpty())
queue.poll()

这一类常见code的吗？
然后有一个回答说他就是用的Queue, Solution里的代码选择用ArrayList是因为Queue里不能加null元素。并且我也觉得原答案想要用到ArrayList的get方法，这也是Queue没有的。但由于BFS的解题模版都是用的Queue,所以我很想学会这种写法。

public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null){
           return "{}";
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        StringBuilder sb = new StringBuilder();
        sb.append("{");
        sb.append(root.val);
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            if (node.left != null){
                sb.append(",");
                sb.append(node.left.val);
                queue.offer(node.left);
            } else{
                sb.append(",#");
            }
            if (node.right != null){
                sb.append(",");
                sb.append(node.right.val);
                queue.offer(node.right);
            } else {
                sb.append(",#");
            }
        }
        sb.append("}");
        return sb.toString();
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.equals("{}")) {
            return null;
        }
        String [] vals = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            for (int i = 1; i < vals.length; i += 2){
                TreeNode node = queue.poll();
                if(!vals[i].equals("#")){
                    node.left = new TreeNode(Integer.parseInt(vals[i]));
                    queue.offer(node.left);        
                }
                if (i + 1 < vals.length && !vals[i + 1].equals("#")){
                    node.right  = new TreeNode(Integer.parseInt(vals[i+1]));
                    queue.offer(node.right);
                }
            }
        }
         return root;
    }
}