😀前言
二叉树是数据结构中的一个重要概念，它在各种算法和应用中广泛使用。然而，当我们需要将二叉树保存到磁盘或在网络中传输时，需要将其转化为一种可存储和传输的格式——这就是序列化的作用。反之，反序列化则是将这种格式还原为原始的二叉树结构。在本文中，我们将介绍如何通过 Java 代码实现二叉树的序列化和反序列化。

😊 序列化二叉树

NowCoder

🥰序列化与反序列化的基本概念

序列化

序列化是指将二叉树按照某种遍历方式转化为字符串的过程。这个字符串能够唯一标识一棵二叉树，以便在需要时能够恢复出与原来相同的二叉树。序列化的方法有多种，如先序遍历、中序遍历、后序遍历或层序遍历。

反序列化

反序列化则是从序列化后的字符串中重新构建二叉树的过程。通过反序列化，我们可以从保存的字符串中还原出与原二叉树结构相同的树。

😋示例解析

问题描述

假设我们有一棵二叉树如下图所示，我们希望通过序列化将其转化为字符串，并通过反序列化从字符串中恢复出原来的二叉树。

对于上图中的二叉树，如果我们选择层序遍历的方式进行序列化，则其结果为{1,2,3,#,#,6,7}，其中#表示空节点。

数据范围：节点数 n≤100，树上每个节点的值满足 0≤val≤150

要求：序列化和反序列化都是空间复杂度 O(n)，时间复杂度 O(n)

🤔Java 实现

接下来，我们将通过 Java 代码演示如何实现二叉树的序列化与反序列化。

private String deserializeStr;

// 序列化函数：将二叉树转换为字符串
public String Serialize(TreeNode root) {
    if (root == null) {
        return "#";
    }
    return root.val + " " + Serialize(root.left) + " " + Serialize(root.right);
}

// 反序列化函数：将字符串还原为二叉树
public TreeNode Deserialize(String str) {
    deserializeStr = str;
    return Deserialize();
}

// 反序列化辅助函数
private TreeNode Deserialize() {
    if (deserializeStr.length() == 0) {
        return null;
    }
    int index = deserializeStr.indexOf(" ");
    String node = index == -1 ? deserializeStr : deserializeStr.substring(0, index);
    deserializeStr = index == -1 ? "" : deserializeStr.substring(index + 1);
    
    if (node.equals("#")) {
        return null;
    }
    
    int val = Integer.valueOf(node);
    TreeNode t = new TreeNode(val);
    t.left = Deserialize();
    t.right = Deserialize();
    return t;
}

代码详解

1. 序列化函数 Serialize：该函数采用先序遍历的方式，将二叉树节点的值逐个存入字符串中。如果节点为空，则用#表示。最终返回包含树结构的字符串。
2. 反序列化函数 Deserialize：反序列化函数从字符串中提取每个节点的值，通过递归的方式重新构建二叉树。由于是先序遍历，左子树会在右子树之前被构建。
3. 辅助函数 Deserialize()：该函数处理反序列化过程中的字符串切割和树的重建工作。它通过空格分割字符串，判断节点值是否为#，从而决定是否继续构建树的子节点。

实例验证

假设输入字符串为{1,2,3,#,#,6,7}，则经过上述代码反序列化后，重新构建的二叉树将与原二叉树完全一致。

2. 输入：{8,6,10,5,7,9,11} 返回值：{8,6,10,5,7,9,11}

😄总结

通过上述代码，我们成功实现了二叉树的序列化与反序列化。这一过程不仅能够将复杂的数据结构转换为易于存储和传输的字符串，还能够在需要时将其还原。无论是在内存优化、网络传输，还是在数据持久化中，这种技术都有着广泛的应用。

在实际项目中，我们可以根据不同的需求选择不同的遍历方式进行序列化与反序列化。同时，理解和掌握这些基础操作，也为处理更复杂的数据结构和算法奠定了坚实的基础。