剑指 Offer 37. 序列化二叉树

题目：请实现两个函数，分别用来序列化和反序列化二叉树。
示例:
你可以将以下二叉树：
1
/ \
2 3
/ \
4 5
序列化为 “[1,2,3,null,null,4,5]”

深度优先搜索，时间复杂度o(n)，空间复杂度o(n)

序列化：前序遍历，使用StringBuilder保存节点值

1. 采用前序遍历的方式，对二叉树的各个节点进行序列化，每个节点值存入一个Stringbuilder中

2. 存放时，需要在节点值后添加一个!表示节点结束，如果出现了null节点则用#!表示

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        // 存放序列化后的结果 
        StringBuilder res = new StringBuilder();
        helpSerialize(root,res);
        return res.toString();
    }
    public void helpSerialize(TreeNode root,StringBuilder res){
        if(root != null){
            res.append(root.val).append("!");
        }else{
            res.append("#!");
            return;
        }
        helpSerialize(root.left,res);
        helpSerialize(root.right,res);
    }

   反序列化：前序遍历，把StringBuilder中保存的值分割后，重新组成新树

3. “!”分割成多个字符串，且设置下标index

4. 每次遇到#时，代表为空，此时index++，且到下一次递归（此处也可以不用下标index，而将数据放到队列中，每次取出队头元素）

5. 最后用当前值创建新节点，且继续递归左右子树

    Integer index = 0;// 反序列化时，当作String数组的下标
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) return null;
        // 拿出有效数据
        String[] split = data.split("!");
        return helpDeserialize(split);
    }
    // 全局下标
    public TreeNode helpDeserialize(String[] strings){
        if(strings[index].equals("#")){
            index++;
            return null;
        }
        if(strings.length == index)
            return null;
        // 当前值作为节点已经被用,index++到达下一个需要反序列化的值
        TreeNode node = new TreeNode(Integer.valueOf(strings[index++]));
        // 先左
        node.left = helpDeserialize(strings);
        // 再右
        node.right = helpDeserialize(strings);
        return node;
    }
    // 队列形式
    public TreeNode deserialize(String data) {
        if(data.isEmpty())
            return null;
        Deque<String> deque = new LinkedList<>(Arrays.asList(data.split("!")));
        return helpDeserialize(deque);
    }
    public TreeNode helpDeserialize(Deque<String> deque){
        String str = deque.poll();
        if(str.equals("#")){
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(str));
        node.left = helpDeserialize(deque);
        node.right = helpDeserialize(deque);
        return node;
    }
   }

   广度优先搜索，时间复杂度o(n)，空间复杂度o(n)

   序列化：使用队列，按照正常方式，使用StringBuilder保存节点值，如果遇到空，则保存为#!

     // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null)
            return "";
        StringBuilder sb = new StringBuilder();
        Deque<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        while(!deque.isEmpty()){
            int sz = deque.size();
            for(int i = 0 ; i < sz ; i++){
                TreeNode node = deque.poll();
                if(node == null){
                    sb.append("#!");
                    continue;
                }
                sb.append(node.val).append("!");
                deque.add(node.left);
                deque.add(node.right);
            }
        }
        return sb.toString();
    }

   反序列化：前序遍历，把StringBuilder中保存的值分割后，将首个值加入到队列中，然后继续依次根据左右节点加入队列，最后重新组成新树

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.isEmpty())
            return null;
        String [] datas = data.split("!");
        Deque<TreeNode> deque = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(datas[0]));
        deque.add(root);
        for(int i = 1 ; i < datas.length ; i++){
            TreeNode node = deque.poll();
            if(!datas[i].equals("#")){
                TreeNode left = new TreeNode(Integer.parseInt(datas[i]));
                node.left = left;
                deque.add(left);
            }
   
            if(!datas[++i].equals("#")){
                TreeNode right = new TreeNode(Integer.parseInt(datas[i]));
                node.right = right;
                deque.add(right);
            }
        }
        return root;
    }