摘要：這里要注意的是的用法。所以記住，用可以從自動(dòng)分離出數(shù)組。跳過(guò)第一個(gè)元素并放入數(shù)組最快捷語(yǔ)句建立的用意記錄處理過(guò)的結(jié)點(diǎn)并按處理所有結(jié)點(diǎn)和自己的連接下面先通過(guò)判斷，再修改的符號(hào)的順序，十分巧妙更輕便的解法

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.

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.

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

這里要注意的是split()的用法。所以記住，用split()可以從String自動(dòng)分離出數(shù)組。

.substring(beginIndex, endIndex) 

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

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;
        }
        
        //跳過(guò)data第一個(gè)元素并放入String數(shù)組最快捷語(yǔ)句
        String[] vals = data.substring(1, data.length() - 1).split(",");
        
        //建立ArrayList的用意：記錄處理過(guò)的結(jié)點(diǎn)
        //并按index處理所有結(jié)點(diǎn)：和自己的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);
            }
            
            //下面先通過(guò)isLeftChild判斷index，
            //再修改isLeftChild的符號(hào)的順序，十分巧妙
            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.