297. 二叉树的序列化与反序列化/面试题37. 序列化二叉树(困难)

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

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

示例:

你可以将以下二叉树：

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree

思路：

BFS

序列化 serialize ：
借助队列，对二叉树做层序遍历，并将越过叶节点的 null 也打印出来。

算法流程：

  1. 特例处理： 若 root 为空，则直接返回空列表 “[]” ；
  2. 初始化： 队列 queue （包含根节点 root ）；序列化列表 res ；
  3. 层序遍历： 当 queue 为空时跳出；
    1. 节点出队，记为 node ；
    2. 若 node 不为空：① 打印字符串 node.val ，② 将左、右子节点加入 queue ；
    3. 否则（若 node 为空）：打印字符串 “null” ；
  4. 返回值： 拼接列表（用 ‘,’ 隔开，首尾添加中括号）。

复杂度分析：
时间复杂度 O(N) ： N 为二叉树的节点数，层序遍历需要访问所有节点，最差情况下需要访问 N + 1个 null ，总体复杂度为 O(2N + 1) = O(N) 。
空间复杂度 O(N) ： 最差情况下，队列 queue 同时存储 2N+1个节点（或 N+1 个 null ），使用O(N) ；列表 res 使用 )O(N) 。

反序列化 deserialize ：
基于本文一开始分析的 “ node , node.left , node.right ” 在序列化列表中的位置关系，可实现反序列化。

利用队列按层构建二叉树，借助一个指针 i 指向节点 node 的左、右子节点，每构建一个 node 的左、右子节点，指针 i 就向右移动 11 位。

算法流程：

  1. 特例处理： 若 data 为空，直接返回 null ；
  2. 初始化： 序列化列表 vals （先去掉首尾中括号，再用逗号隔开），指针 i=1 ，根节点 root （值为 vals[0] ），队列 queue（包含 root ）；
  3. 按层构建： 当 queue 为空时跳出；
    1. 节点出队，记为 node ；
    2. 构建 node 的左子节点：node.left 的值为 vals[i] ，并将 node.left 入队；
    3. 执行 i+=1 ；
    4. 构建 node 的右子节点：node.left 的值为 vals[i] ，并将 node.right入队；
    5. 执行 i+=1 ；
  4. 返回值： 返回根节点 root 即可。

复杂度分析：
时间复杂度 O(N) ： N 为二叉树的节点数，按层构建二叉树需要遍历整个 vals ，其长度最大为 2N+1 。
空间复杂度 O(N) ： 最差情况下，队列 queue 同时存储 2N+1个节点，因此使用 O(N) 额外空间。

作者：jyd
链接：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/solution/mian-shi-ti-37-xu-lie-hua-er-cha-shu-ceng-xu-bian-/

值得多看，特别是反序列化中的细节

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/**
 * 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) {
        if(root==null){
            return "";
        }
        //非递归解法
        Queue<TreeNode> queue = new LinkedList<>();
        StringBuilder res = new StringBuilder();
        //根节点入队列
        queue.offer(root);
        while(!queue.isEmpty()){
            //出队，判断
            TreeNode out = queue.poll();
            if(out!=null){
                res.append(out.val+",");
                //将左右添加进来
                queue.add(out.left);
                queue.add(out.right);
            }else{
                res.append("null,");
            }
        }
        return res.toString();
    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.isEmpty()){
            return null;
        }
        String[] nodes = data.split(",");
        //层次遍历第一个还是根节点
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        //反序列化还是队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        for(int i=1;i< nodes.length;){
            //在队中的是父节点
            TreeNode parent = queue.poll();
            //旁边的是左节点
            String left = nodes[i++];
            if(!left.equals("null")){
                parent.left = new TreeNode(Integer.parseInt(left));
                //将其加入队
                queue.offer(parent.left);
            }else {
                parent.left = null;
            }
            //再旁边一个是右节点
            String right = nodes[i++];
            if(!right.equals("null")){
                parent.right = new TreeNode(Integer.parseInt(right));
                //将其加入队
                queue.offer(parent.right);
            }else {
                parent.right = null;
            }
        }
        return root;
    }
}

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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();
    }
    //辅助函数
    void serialize(TreeNode root,StringBuilder sb){
        if(root==null){
            sb.append("null,");
            return;
        }
        //前序遍历
        sb.append(root.val+",");
        serialize(root.left,sb);
        serialize(root.right,sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        //将字符串，拆成链表
        LinkedList<String> node = new LinkedList<>();
        for (String s : data.split(",")){
            node.addLast(s);
        }
        return deserialize(node);
    }
    //辅助函数
    TreeNode deserialize(LinkedList<String> node){
        if(node.isEmpty()){
            return null;
        }
        //根据前序遍历特点排列节点
        String node1 = node.removeFirst();
        if(node1.equals("null")){
            return null;
        }
        //将第一个节点还原
        TreeNode root = new TreeNode(Integer.parseInt(node1));
        //这里不是很理解
        root.left = deserialize(node);
        root.right = deserialize(node);
        return root;
    }
}