关于java:offer-37-序列化二叉树

序列化二叉树

通常应用的前序、中序、后序、层序遍历记录的二叉树的信息不残缺，即 惟一的输入序列可能对应着多种二叉树 可能性。

• 察看题目示例，序列化的字符串实际上是二叉树的“层序遍历”（BFS）后果，本文也采纳层序遍历。

题目剖析

能够发现法则


序列化 应用层序遍历实现。 反序列化 通过以上递推公式反推各节点在序列中的索引，进而实现。
序列化和反序列化

• Java 序列化就是指把 Java 对象转换为字节序列的过程
• Java 反序列化就是指把字节序列复原为 Java 对象的过程。

留神 **

• 为残缺示意二叉树，思考将叶节点下的 null 也记录 **
• stringObject.substring(start,stop): 一个新的字符串，该字符串值蕴含 stringObject 的一个子字符串，其内容是从 start 处到 stop-1 处的所有字符，其长度为 stop 减 start。就是坐标范畴是左闭右开，不包含 stop 那个索引对应的字符

题解

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) {val = x;}
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    // 这个是序列化
    public String serialize(TreeNode root) {
        // 利用队列进行打印，并且须要把 null 的也打印进去
        if(root == null) return "[]";// 要留神办法的返回类型是 String
        StringBuilder res = new StringBuilder("[");// 定义一个字符串缓冲流先把左侧括号加进去
        // 定义一个队列用于退出字符串，并且还要先把根节点加进去，也能够不加前面单写一行加
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        while(!queue.isEmpty()){
            //poll 从队列头部删除一个元素。队列是空的时候会返回 null
            TreeNode node = queue.poll();
            // 如果以后节点不是空的就退出字符串
            if(node != null) {
                // 而后出栈的节点的值退出字符缓冲流对象 还要记得加都好，时刻记得这是字符串
                res.append(node.val+",");
                // 而后把以后节点的左右节点持续入栈
                queue.add(node.left);
                queue.add(node.right);
            }else{res.append("null,");}// 如果是空的也要退出 null
        }
        // 依照层排列结束了
        res.deleteCharAt(res.length() - 1);// 要把最初一个字符串前面一起的那个逗号删掉
        res.append("]");// 删掉之后再把数组的另一半字符串加到下面
        return res.toString();// 而后再把字符缓冲流变成字符串}

    // Decodes your encoded data to tree.
    // 这个是反序列化
    public TreeNode deserialize(String data) {
        // 反序列化就是把输出的字符串再换成节点
        if(data.equals("[]") ) return null;
        // 将输出的一长串字符串用，裁进去取 1 是去掉一开始的 0 索引下的[符号
        String[] str = data.substring(1,data.length() - 1).split(",");
        // 因为序列化也是一层一层的，所以第一个字符就是根节点
        TreeNode root = new TreeNode(Integer.parseInt(str[0]));// 将字符串里的数字字符转化成数字再变成节点
        // 定义一个链表，先把根节点存进去
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        int i = 1;
        while(!queue.isEmpty()){
            //poll 从队列头部删除一个元素。队列是空的时候会返回 null
            TreeNode node = queue.poll();
            // 如果下一个字符的值不是 null
            if(!str[i].equals("null")){
                // 那以后节点的左节点 就是这个值
                node.left = new TreeNode(Integer.parseInt(str[i]));
                // 而后再把以后节点的左节点加进去
                queue.add(node.left);
            }
            i++;
            if(!str[i].equals("null")){
                // 那以后节点的左节点 就是这个值
                node.right = new TreeNode(Integer.parseInt(str[i]));
                // 而后再把以后节点的左节点加进去
                queue.add(node.right);
            }
            i++;
        }
        return root; 
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

还有一个速度比拟快的答案，用了递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) {val = x;}
 * }
 */
public class Codec {

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

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {if(data == null || data.length() == 0)  return null;
        String[] s = data.split(",");
        LinkedList<String> nodes = new LinkedList<>();
        for(String str : s){nodes.addLast(str);
        }
        return deserialize(nodes);
    }
    public TreeNode deserialize(LinkedList<String> nodes){if(nodes.isEmpty()) return null;
        String first = nodes.removeFirst();
        if(first.equals("null")) return null;
        TreeNode root = new TreeNode(Integer.parseInt(first));
        root.left = deserialize(nodes);
        root.right = deserialize(nodes);
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));