Leetcode:297. 二叉树的序列化与反序列化

题目描述

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例:

你可以将以下二叉树：

 1
/ \
2   3
    / \
    4   5

序列化为 "[1,2,3,null,null,4,5]"

提示:

这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

说明:

不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。

思路

思路1: BFS + 迭代

使用队列进行BFS，记录每个节点进行迭代

思路2: BFS + 递归（TODO:）

代码

代码1

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        Queue queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode pre = queue.poll();
            if (pre == null){
                sb.append("n");
                sb.append(",");
                continue;
            }else{
                sb.append(String.valueOf(pre.val));
                sb.append(",");
            }
            queue.offer(pre.left);
            queue.offer(pre.right);
        }
        int neededLength = sb.length() - 1;
        // strip speed
        while(neededLength > 2 && sb.charAt(neededLength - 1) == 'n'){
            neededLength -= 2;
        }
        sb.setLength(neededLength);
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.equals("n")){
            return null;
        }
        String[] vals = data.split(",");
        TreeNode root = new TreeNode(Integer.valueOf(vals[0]));
        Queue queue = new LinkedList<>();
        queue.offer(root);
        for(int i = 1; i < vals.length; i += 2){
            if (queue.isEmpty()){
                break;
            }
            TreeNode pre = queue.poll();
            if (vals[i].equals("n")){
                pre.left = null;
            }else{
                TreeNode left = new TreeNode(Integer.valueOf(vals[i]));
                pre.left = left;
                queue.offer(left);
            }
            if (i + 1 >= vals.length){
                break;
            }
            if (vals[i + 1].equals("n")){
                pre.right = null;
            }else{
                TreeNode right = new TreeNode(Integer.valueOf(vals[i + 1]));
                pre.right = right;
                queue.offer(right);
            }
        }
        return root;
    }
}