二叉树序列化与反序列化

在这里插入图片描述

在实际开发中，经常需要将二叉树保存到文件或通过网络传输。这就需要将树结构转换为字符串（序列化），以及从字符串恢复树结构（反序列化）。

今天就来剖析这个序列化和反序列化的问题。

🚀解题思路

🟦 用 前序遍历（根→左→右） 把树“拍扁”成字符串 🟦 用 # 表示空节点 🟦 反序列化时，递归按顺序读回来

这样就能保证序列化和反序列化是一一对应的。

💻 完整代码

 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


public class Codec {

    // 序列化：将二叉树转成字符串
    public String serialize(TreeNode root) {
        StringBuilder builder = new StringBuilder();
        f(root, builder);
        return builder.toString();
    }

    // 前序遍历构建字符串
    void f(TreeNode root, StringBuilder builder) {
        if (root == null) {
            builder.append("#,");  // 用#表示null节点
        } else {
            builder.append(root.val + ",");  // 当前节点值
            f(root.left, builder);           // 递归左子树
            f(root.right, builder);          // 递归右子树
        }
    }

    // 反序列化：将字符串还原为二叉树
    public TreeNode deserialize(String data) {
        String[] vals = data.split(",");
        cnt = 0;
        return g(vals);
    }

    // 当前解析到数组的第几个元素
    public static int cnt;

    // 递归构建树
    TreeNode g(String[] vals) {
        String cur = vals[cnt++];
        if (cur.equals("#")) {
            return null;  // 空节点
        } else {
            TreeNode head = new TreeNode(Integer.valueOf(cur));
            head.left = g(vals);
            head.right = g(vals);
            return head;
        }
    }
}

如果觉得有帮助，欢迎点赞、关注、转发~