剑指offer-61、序列化二叉树

题⽬描述

请实现两个函数，分别⽤来序列化和反序列化⼆叉树
⼆叉树的序列化是指：把⼀棵⼆叉树按照某种遍历⽅式的结果以某种格式保存为字符串，从⽽使得内存中建⽴起来的⼆叉树可以持久保存。序列化可以基于先序、中序、后序、层序的⼆叉树遍历⽅式来进⾏修改，序列化的结果是⼀个字符串，序列化时通过 某种符号表示空节点（ # ），以 ！ 表示⼀个结点值的结束（ value! ）。
⼆叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str ，重构⼆叉树。例如，我们可以把⼀个只有根节点为1的⼆叉树序列化为" 1"，然后通过⾃⼰的函数来解析回这个⼆叉树
示例1
输⼊：{8,6,10,5,7,9,11}
返回值：{8,6,10,5,7,9,11}
思路及解答

前序遍历（递归）

利用二叉树的前序遍历顺序（根-左-右）进行序列化，并使用特殊字符（如"#"或"null"）表示空节点，以确保树结构的唯一性。
序列化思路：从根节点开始，先输出当前节点的值，然后递归地序列化左子树和右子树。遇到空节点时，输出空标记（如"#"）。
反序列化思路：按照前序遍历的顺序，依次从序列化字符串中读取节点值。如果读取到空标记，则返回null；否则，用当前值创建节点，并递归构建其左子树和右子树

1. public class CodecPreOrder {
3.     // 序列化：将二叉树转换为字符串
4.     public String serialize(TreeNode root) {
5.         StringBuilder sb = new StringBuilder();
6.         buildString(root, sb);
7.         // 删除末尾多余的分隔符（如果有）
8.         if (sb.length() > 0) {
9.             sb.setLength(sb.length() - 1);
10.         }
11.         return sb.toString();
12.     }
14.     private void buildString(TreeNode node, StringBuilder sb) {
15.         if (node == null) {
16.             sb.append("#").append(","); // 使用"#"表示空节点
17.             return;
18.         }
19.         sb.append(node.val).append(","); // 先处理根节点
20.         buildString(node.left, sb);     // 再递归处理左子树
21.         buildString(node.right, sb);    // 最后递归处理右子树
22.     }
24.     // 反序列化：将字符串还原为二叉树
25.     public TreeNode deserialize(String data) {
26.         if (data == null || data.isEmpty()) return null;
27.         // 将字符串按分隔符分割成列表
28.         LinkedList<String> nodes = new LinkedList<>(Arrays.asList(data.split(",")));
29.         return buildTree(nodes);
30.     }
32.     private TreeNode buildTree(LinkedList<String> nodes) {
33.         if (nodes.isEmpty()) return null;
34.         String val = nodes.removeFirst(); // 按前序顺序取出节点值
35.         if (val.equals("#")) return null; // 遇到空标记则返回null
36.         
37.         TreeNode root = new TreeNode(Integer.parseInt(val));
38.         root.left = buildTree(nodes);  // 递归构建左子树
39.         root.right = buildTree(nodes); // 递归构建右子树
40.         return root;
41.     }
42. }

复制代码

• 时间复杂度：O(n)，每个节点恰好被访问一次。
  
• 空间复杂度：O(n)，递归调用栈的深度在最坏情况下（树退化为链表）为O(n)，序列化字符串长度也与节点数n成线性关系。
  

层序遍历（迭代）

层序遍历（广度优先搜索）更直观，可以按层级顺序处理节点，适合处理接近完全二叉树的情况。
序列化思路：使用队列辅助进行层序遍历。从根节点开始，将节点值加入字符串，并将其非空子节点（即使是空节点也记录）加入队列，以确保树结构信息完整。
反序列化思路：同样使用队列，根据序列化字符串的顺序，依次为每个非空节点创建其左右子节点

1. public class CodecLevelOrder {
3.     // 序列化：层序遍历二叉树
4.     public String serialize(TreeNode root) {
5.         if (root == null) return "";
6.         StringBuilder sb = new StringBuilder();
7.         Queue<TreeNode> queue = new LinkedList<>();
8.         queue.offer(root);
9.         
10.         while (!queue.isEmpty()) {
11.             TreeNode node = queue.poll();
12.             if (node == null) {
13.                 sb.append("#,"); // 空节点标记
14.                 continue;
15.             }
16.             sb.append(node.val).append(",");
17.             // 即使子节点为空也加入队列，以保留结构信息
18.             queue.offer(node.left);
19.             queue.offer(node.right);
20.         }
21.         // 移除末尾多余的分隔符
22.         sb.setLength(sb.length() - 1);
23.         return sb.toString();
24.     }
26.     // 反序列化：根据层序序列重建树
27.     public TreeNode deserialize(String data) {
28.         if (data == null || data.isEmpty()) return null;
29.         String[] values = data.split(",");
30.         if (values[0].equals("#")) return null;
31.         
32.         TreeNode root = new TreeNode(Integer.parseInt(values[0]));
33.         Queue<TreeNode> queue = new LinkedList<>();
34.         queue.offer(root);
35.         int index = 1; // 指向当前待处理子节点的数组位置
36.         
37.         while (!queue.isEmpty() && index < values.length) {
38.             TreeNode parent = queue.poll();
39.             // 构建左子节点
40.             if (index < values.length && !values[index].equals("#")) {
41.                 parent.left = new TreeNode(Integer.parseInt(values[index]));
42.                 queue.offer(parent.left);
43.             }
44.             index++;
45.             // 构建右子节点
46.             if (index < values.length && !values[index].equals("#")) {
47.                 parent.right = new TreeNode(Integer.parseInt(values[index]));
48.                 queue.offer(parent.right);
49.             }
50.             index++;
51.         }
52.         return root;
53.     }
54. }

复制代码

• 时间复杂度：O(n)，每个节点入队、出队各一次。
  
• 空间复杂度：O(n)，队列中最多同时存储约n/2个节点（完全二叉树的最后一层）。
  

二叉搜索树（BST）前序优化

对于二叉搜索树（BST），可以利用其中序遍历为升序的特性，仅通过前序或后序序列即可唯一确定树结构，无需显式存储空节点。
序列化思路：对BST进行前序遍历，将节点值拼接成字符串。由于BST的性质，中序遍历就是节点值的升序排列，因此仅凭前序遍历结果就能唯一确定树结构。
反序列化思路：根据前序遍历结果，第一个元素为根节点。剩余元素中，所有小于根节点的值构成左子树的前序遍历，大于根节点的值构成右子树的前序遍历。递归进行即可重建BST
[code]public class CodecBST {    // 序列化：对BST进行前序遍历    public String serialize(TreeNode root) {        if (root == null) return "";        StringBuilder sb = new StringBuilder();        preorderTraversal(root, sb);        return sb.substring(0, sb.length() - 1); // 去掉末尾分隔符    }    private void preorderTraversal(TreeNode node, StringBuilder sb) {        if (node == null) return;        sb.append(node.val).append(" "); // 用空格分隔，注意BST序列化可不显式标记空节点        preorderTraversal(node.left, sb);        preorderTraversal(node.right, sb);    }    // 反序列化：利用BST性质重建树    public TreeNode deserialize(String data) {        if (data.isEmpty()) return null;        // 将字符串转换为整数列表        int[] values = Arrays.stream(data.split(" ")).mapToInt(Integer::parseInt).toArray();        return buildBST(values, 0, values.length - 1);    }    private TreeNode buildBST(int[] preorder, int start, int end) {        if (start > end) return null;        TreeNode root = new TreeNode(preorder[start]);        // 找到右子树的开始索引（第一个大于根节点值的元素）        int rightStart = start + 1;        while (rightStart