40_序列化二叉树

要求：请实现两个函数，分别用来序列化和反序列化二叉树。

g

思路： 利用层次遍历BFS，借助队列
二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
序列化：借助队列，对二叉树做层序遍历，并将越过叶节点的 null也打印出来。
反序列化：基于本文一开始分析的 “ node , node.left , node.right ” 在序列化列表中的位置关系，可实现反序列化。利用队列按层构建二叉树，借助一个指针 ii 指向节点 node 的左、右子节点，每构建一个 node 的左、右子节点，指针 i 就向右移动 1 位。

public class Codec {
    // Encodes a tree to a single string.
// 序列化
    public String serialize(TreeNode root) {
        // 判断边界
        if(root==null)return "[]";
        Queue<TreeNode> queue = new LinkedList<>();
        // 将root加入到队列当中
        queue.add(root);
        // 初始化一个字符串操作对象，形式如下“[”
        StringBuilder str = new StringBuilder("[");
        while(!queue.isEmpty()){
            // 取出队列中的元素
            TreeNode node = queue.poll();
            if(node!=null){ 
                // 不为空时，往“[”后面添加二叉树的值+","，层次遍历
                str.append(node.val+",");
                // 往队列中添加左子节点和右子节点
                queue.add(node.left);
                queue.add(node.right);
            }else{
                // 为空时，往“[”后添加“null,”
                str.append("null,");
            }
        }
        // 删除掉最后一个字符“,”
        str.deleteCharAt(str.length()-1);
        // “]”闭合上
        str.append("]");
        return str.toString();
    }
// 反序列化
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.equals("[]"))return null;
        // 对data字符串进行处理，转换为数组,先将收尾[]去掉，然后以及，分割成数组
        String[] str = data.substring(1,data.length()-1).split(",");
        Queue<TreeNode> queue = new LinkedList<>();
        // 将字符串转为整型，并转换为TreeNode类型
        TreeNode root = new TreeNode(Integer.parseInt(str[0]));
        queue.add(root);
        int i = 1;
        while(!queue.isEmpty()){
            // 从队列中取出一个节点
            TreeNode node = queue.poll();
            if(!str[i].equals("null")){
                // 添加左子节点到node下
                node.left = new TreeNode(Integer.parseInt(str[i]));
                queue.add(node.left);
            }
            // 字符数组往后移动一位
            i++;
            if(!str[i].equals("null")){
                // 添加左子节点到node下
                node.right = new TreeNode(Integer.parseInt(str[i]));
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }
}