二叉树状态持久化本质是将其内存中的节点值、左右子树关联关系转换为可存储或传输的字符串格式，再通过反序列化将字符串还原为原始二叉树结构。实现过程中需要同时保证节点变量值和树形层级关系不丢失，才能做到完整恢复。
序列化核心设计原则
要实现变量结构完整恢复，序列化规则需要满足两个核心条件：
- 能够明确记录每个节点的变量值，包括空节点的标识，避免结构错位
- 能够明确还原节点的左右子树关联关系，保证树的层级和原始结构一致
常用的序列化方式分为前序序列化、层序序列化两类，下面分别介绍实现方法。
前序遍历序列化实现
前序遍历的顺序是根节点、左子树、右子树，我们用#标识空节点，用逗号分隔每个节点的值，这样反序列化时按照前序顺序读取就能还原结构。
二叉树节点定义
首先定义基础的二叉树节点结构，包含节点值、左子节点、右子节点三个变量：
// 二叉树节点定义
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
前序序列化方法
递归遍历二叉树，将节点值拼接为字符串，空节点拼接#：
public class BinaryTreeSerialize {
// 前序序列化方法
public static String preorderSerialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
preorderHelper(root, sb);
return sb.toString();
}
private static void preorderHelper(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append("#,");
return;
}
// 拼接当前节点值
sb.append(node.val).append(",");
// 递归处理左子树
preorderHelper(node.left, sb);
// 递归处理右子树
preorderHelper(node.right, sb);
}
}
前序反序列化方法
将序列化后的字符串按逗号分割为数组，按照前序顺序递归还原节点，遇到#则返回空节点：
public class BinaryTreeSerialize {
// 前序反序列化方法
public static TreeNode preorderDeserialize(String data) {
if (data == null || data.length() == 0) {
return null;
}
String[] nodes = data.split(",");
int[] index = new int[]{0};
return preorderDeserializeHelper(nodes, index);
}
private static TreeNode preorderDeserializeHelper(String[] nodes, int[] index) {
if (index[0] >= nodes.length) {
return null;
}
String val = nodes[index[0]];
index[0]++;
if ("#".equals(val)) {
return null;
}
// 还原当前节点
TreeNode node = new TreeNode(Integer.parseInt(val));
// 还原左子树
node.left = preorderDeserializeHelper(nodes, index);
// 还原右子树
node.right = preorderDeserializeHelper(nodes, index);
return node;
}
}
层序遍历序列化实现
层序遍历按照树的层级从上到下、从左到右遍历节点，同样用#标识空节点，用逗号分隔值，反序列化时通过队列辅助还原结构。
层序序列化方法
使用队列存储待处理的节点，依次遍历每一层节点，拼接节点值：
import java.util.LinkedList;
import java.util.Queue;
public class BinaryTreeSerialize {
// 层序序列化方法
public static String levelSerialize(TreeNode root) {
if (root == null) {
return "#,";
}
StringBuilder sb = new StringBuilder();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node == null) {
sb.append("#,");
continue;
}
sb.append(node.val).append(",");
// 左子节点入队，即使为空也入队保证结构
queue.offer(node.left);
queue.offer(node.right);
}
return sb.toString();
}
}
层序反序列化方法
将字符串分割为节点数组，用队列存储已还原的父节点，依次给父节点绑定左右子节点：
import java.util.LinkedList;
import java.util.Queue;
public class BinaryTreeSerialize {
// 层序反序列化方法
public static TreeNode levelDeserialize(String data) {
if (data == null || data.length() == 0) {
return null;
}
String[] nodes = data.split(",");
if ("#".equals(nodes[0])) {
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int index = 1;
while (!queue.isEmpty() && index < nodes.length) {
TreeNode parent = queue.poll();
// 还原左子节点
if (!"#".equals(nodes[index])) {
parent.left = new TreeNode(Integer.parseInt(nodes[index]));
queue.offer(parent.left);
}
index++;
// 还原右子节点
if (index < nodes.length && !"#".equals(nodes[index])) {
parent.right = new TreeNode(Integer.parseInt(nodes[index]));
queue.offer(parent.right);
}
index++;
}
return root;
}
}
两种序列化方式对比
两种方式都能实现二叉树状态持久化和完整结构恢复，适用场景略有不同：
| 序列化方式 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| 前序序列化 | 递归实现简单，代码逻辑清晰 | 反序列化也需要递归，深度过大的树可能出现栈溢出 | 树深度较小，追求代码简洁的场景 |
| 层序序列化 | 迭代实现，无栈溢出风险，符合树的层级结构 | 需要额外队列存储节点，实现逻辑稍复杂 | 树深度较大，需要稳定还原结构的场景 |
注意事项
- 序列化分隔符可以根据需求调整，只要保证序列化和反序列化使用相同的分隔规则即可
- 如果节点值包含特殊字符，需要提前做转义处理，避免和分隔符冲突
- 反序列化前需要校验序列化字符串的合法性，避免空指针或格式错误导致的异常
二叉树状态持久化的核心是序列化规则的设计，只要保证空节点和结构关系都能被正确记录，就能实现变量和结构的完整恢复，开发者可以根据实际场景选择合适的序列化方式。