297-二叉树的序列化和反序列化
数据结构和算法
6 分钟 读完 (大约 828 个字) 0次访问

297-二叉树的序列化和反序列化

力扣297 / 剑指offer37

https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/

Java 优化后稳定12ms

1
2
3
4
5
6
7
8
你可以将以下二叉树：
     1
    / \
   2   3
  /   /
 4   5

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

这是一道困难题，题目没有要求采用什么顺序进行序列化，只要能序列化能还原就行

示例用的是层次遍历，其实力扣以前的树题目也都是采用这个，本文也采用这个


我的BFS解法

serialize()：将二叉树层次遍历序列化为字符串

要注意和普通的bfs模板不同的地方：

  1. 去掉if(cur.left != null)，要把null也加进来，并append(“null,”)

  2. 第一步改造后会在queue的末尾产生多余null值（1,2,3,4,null,5,null），要去除多余的null则需改变while结束条件：记录有效节点数而不是!queue.isEmpty()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public String serialize(TreeNode root) {
        if (root == null) return "[]";
        StringBuilder sb = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int validNum = 1;   //记录有效节点数
        while (validNum != 0){
            TreeNode cur = queue.poll();
            if (cur != null){
                validNum--;
                sb.append(cur.val);
                queue.offer(cur.left);  //null也加进来
                if (cur.left != null) validNum++;   //null不计入有效节点
                queue.offer(cur.right);  //null也加进来
                if (cur.right != null) validNum++;   //null不计入有效节点
            }else {
                sb.append("null");
            }
            if (validNum != 0) sb.append(",");
        }
        sb.append("]");
        return sb.toString();
    }

优化了一下，if (validNum != 0) sb.append(",");原来使用sb.setLength内部还是调用了Arrays.fill，里面是循环，原来在12-16ms波动


deserialize()：反序列化，用层次遍历字符串序列重构二叉树

遍历一遍，因为字符串是记录了null的，因此肯定是一左一右，树这边，需要用队列记录根节点才知道挂到哪一棵树上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public TreeNode deserialize(String data) {
    if (data.equals("[]")) return null;
    String[] nodes = data.substring(1, data.length() - 1).split(",");
    TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int i = 0;
    while (i < nodes.length){
        TreeNode cur = queue.poll();
        i++;
        if (i < nodes.length && !"null".equals(nodes[i])){
            cur.left = new TreeNode(Integer.parseInt(nodes[i]));
            queue.offer(cur.left);
        }
        i++;
        if (i < nodes.length && !"null".equals(nodes[i])){
            cur.right = new TreeNode(Integer.parseInt(nodes[i]));
            queue.offer(cur.right);
        }
    }
    return root;
}

DFS解法

我看到时间短的解法都是DFS，我也没有做，找了个提交记录2ms的，有时间再看，记录一下

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
public class Codec {

    // Encodes a tree to a single string.
    StringBuilder res;
    int i ;

    public String serialize(TreeNode root) {
        res = new StringBuilder();
        serializeDFS(root);
        return res.toString();
    }

    public void serializeDFS(TreeNode root) {
        if (root==null) {
            res.append("#");
            return ;
        }
        res.append((char) (root.val+'0'));
        serializeDFS(root.left);
        serializeDFS(root.right);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
       return deserializeDFS(data.toCharArray());
    }

    public TreeNode deserializeDFS(char[] chars) {
        if (chars[i]=='#') {
            i++;
            return null;
        }
        TreeNode root = new TreeNode(chars[i++]-'0');
        root.left = deserializeDFS(chars);
        root.right = deserializeDFS(chars);
        return root;
    }
}

娱乐解法

提交完后我去提交记录里看了看0ms和1ms的示例…

以下代码仅供娱乐

0ms 笑死我了，真是人才，由于不限定序列化的方式，因此判题系统只判断deserialize函数

1
2
3
4
5
6
7
8
9
10
11
12
public class Codec {
	TreeNode node;

    public String serialize(TreeNode root) {
        node = root;
        return " ";
    }

    public TreeNode deserialize(String data) {
        return node;
    }
}

32ms c语言强转，看起来可行，但实际上是在内存中取地址，跨机发送和网络传输地址不同不可行

1
2
3
4
5
6
7
char* serialize(struct TreeNode* root) {
    return (char *)root;
}

struct TreeNode* deserialize(char* data) {
    return (struct TreeNode *)data;
}

其他树的题目点击这里

# ,
Quill笔记
116/117-填充每个节点的下一个右侧节点指针
关注我

分类

标签云

DL/ML http lintcode markdown mysql spring springcloud 二分查找 剑指offer 力扣 加密 动态规划 单调栈 回溯 字符串 学习记录 开发 排序 数据结构 栈 树 游戏和引擎 笔试 笔试面试 算法 递归

推荐阅读

推荐阅读

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×