[LintCode/LeetCode] Binary Tree Serialization

Problem
Design an algorithm and write code to serialize and deserialize a binary tree. Writing the tree to a file is called 'serialization' and reading back from the file to reconstruct the exact same binary tree is 'deserialization'.
There is no limit of how you deserialize or serialize a binary tree, you only need to make sure you can serialize a binary tree to a string and deserialize this string to the original structure.
Example
An example of testdata: Binary tree {3,9,20,#,#,15,7} denote the following structure:

  3
 / \
9  20
  /  \
 15   7

Our data serialization use bfs traversal. This is just for when you got wrong answer and want to debug the input.You can use other method to do serializaiton and deserialization.
Note

String[] vals = data.substring(1, data.length() - 1).split(",");  

여기 서 주의해 야 할 것 은 split() 의 용법 이다.따라서 split () 로 String 에서 배열 을 자동 으로 분리 할 수 있다 는 것 을 기억 하 세 요.

.substring(beginIndex, endIndex) 

beginIndex(Inclusive), endIndex(exclusive). So, the '{' and '}' are not included in vals[].
Solution

class Solution {

    public String serialize(TreeNode root) {
        if (root == null) {
            return "{}";
        }
        ArrayList queue = new ArrayList();
        queue.add(root);
        for (int i = 0; i < queue.size(); i++) {
            TreeNode node = queue.get(i);
            if (node == null) {
                continue;
            }
            queue.add(node.left);
            queue.add(node.right);
        }
        
        //Of course we can delete this.
        /*
        while (queue.get(queue.size() - 1) == null) {
            queue.remove(queue.size() - 1);
        }
        */
        
        StringBuilder sb = new StringBuilder();
        sb.append("{");
        sb.append(queue.get(0).val);//remember to add .val
        for (int i = 1; i < queue.size(); i++) {
            if (queue.get(i) == null) {
                sb.append(",#");
            } else {
                sb.append(",");
                sb.append(queue.get(i).val);
            }
        }
        sb.append("}");
        return sb.toString(); //sb is not String, we have to transform
    }

    public TreeNode deserialize(String data) { //more tricky!
        if (data.equals("{}")) {
            return null;
        }
        
        //  data        String       
        String[] vals = data.substring(1, data.length() - 1).split(",");
        
        //  ArrayList   ：        
        //  index      ：    children  
        ArrayList queue = new ArrayList();
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        queue.add(root);
        int index = 0;
        boolean isLeftChild = true;
        for (int i = 1; i < vals.length; i++) {
            if (!vals[i].equals("#")) {
                //vals[i] is a String, so use parseInt()
                TreeNode node = new TreeNode(Integer.parseInt(vals[i]));
                if (isLeftChild) {
                    queue.get(index).left = node;
                } else {
                    queue.get(index).right = node;
                }
                queue.add(node);
            }
            
            //     isLeftChild  index，
            //   isLeftChild      ，    
            if (!isLeftChild) {
                index++;
            }
            isLeftChild = !isLeftChild;
        }
        return root;
    }
}

더 가 벼 운 해법

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "null";
        StringBuilder sb = new StringBuilder();
        sb.append(root.val);
        String left = serialize(root.left);
        String right = serialize(root.right);
        sb.append(","+left+","+right);
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] strs = data.split(",");
        Queue q = new LinkedList<>();
        for (String str: strs) {
            q.offer(str);
        }
        return helper(q);
    }
    
    public TreeNode helper(Queue q) {
        String str = q.poll();
        if (str.equals("null")) return null;
        TreeNode root = new TreeNode(Integer.parseInt(str));
        root.left = helper(q);
        root.right = helper(q);
        return root;
    }
}

For this problem, we are required to implement two methods: serialization and deserialization.
For the serialization part, we are given a TreeNode root . First of all, I am gonna check whether the root is null because I will use a recursion for this method. And I will create a StringBuilder, sb , to store the value of each node. I will first append root.val to the StringBuilder. Then I will do the recursion twice, for root.left and root.right , to get left child part and right child part done. Next, I will arrange them with comma.
For the deserialization part, we are given a String of data (values of nodes). First, I will use data.split(",") method to separate data into String array . To use DFS, we will restructure this String array by using Queue , as Queue has FIFO property. So we put the String array into the Queue q , and call its DFS function for q .In DFS function, we know that nodes in q are distributed into left part and right part. This would make the recursion simple by directly calling recursion for root.left and root.right as q is ordered.