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

请实现两个函数分别⽤来序列化和反序列化⼆叉树⼆叉树的序列化是指把⼀棵⼆叉树按照某种遍历⽅式的结果以某种格式保存为字符串从⽽使得内存中建⽴起来的⼆叉树可以持久保存。序列化可以基于先序、中序、后序、层序的⼆叉树遍历⽅式来进⾏修改序列化的结果是⼀个字符串序列化时通过 某种符号表示空节点 # 以 表示⼀个结点值的结束 value! 。⼆叉树的反序列化是指根据某种遍历顺序得到的序列化字符串结果str 重构⼆叉树。例如我们可以把⼀个只有根节点为1的⼆叉树序列化为 1然后通过⾃⼰的函数来解析回这个⼆叉树示例1输⼊{8,6,10,5,7,9,11}返回值{8,6,10,5,7,9,11}思路及解答前序遍历递归利用二叉树的前序遍历顺序根-左-右进行序列化并使用特殊字符如#或null表示空节点以确保树结构的唯一性。序列化思路从根节点开始先输出当前节点的值然后递归地序列化左子树和右子树。遇到空节点时输出空标记如#。反序列化思路按照前序遍历的顺序依次从序列化字符串中读取节点值。如果读取到空标记则返回null否则用当前值创建节点并递归构建其左子树和右子树javapublic class CodecPreOrder { // 序列化将二叉树转换为字符串 public String serialize(TreeNode root) { StringBuilder sb new StringBuilder(); buildString(root, sb); // 删除末尾多余的分隔符如果有 if (sb.length() 0) { sb.setLength(sb.length() - 1); } return sb.toString(); } private void buildString(TreeNode node, StringBuilder sb) { if (node null) { sb.append(#).append(,); // 使用#表示空节点 return; } sb.append(node.val).append(,); // 先处理根节点 buildString(node.left, sb); // 再递归处理左子树 buildString(node.right, sb); // 最后递归处理右子树 } // 反序列化将字符串还原为二叉树 public TreeNode deserialize(String data) { if (data null || data.isEmpty()) return null; // 将字符串按分隔符分割成列表 LinkedListString nodes new LinkedList(Arrays.asList(data.split(,))); return buildTree(nodes); } private TreeNode buildTree(LinkedListString nodes) { if (nodes.isEmpty()) return null; String val nodes.removeFirst(); // 按前序顺序取出节点值 if (val.equals(#)) return null; // 遇到空标记则返回null TreeNode root new TreeNode(Integer.parseInt(val)); root.left buildTree(nodes); // 递归构建左子树 root.right buildTree(nodes); // 递归构建右子树 return root; } }时间复杂度O(n)每个节点恰好被访问一次。空间复杂度O(n)递归调用栈的深度在最坏情况下树退化为链表为O(n)序列化字符串长度也与节点数n成线性关系。层序遍历迭代层序遍历广度优先搜索更直观可以按层级顺序处理节点适合处理接近完全二叉树的情况。序列化思路使用队列辅助进行层序遍历。从根节点开始将节点值加入字符串并将其非空子节点即使是空节点也记录加入队列以确保树结构信息完整。反序列化思路同样使用队列根据序列化字符串的顺序依次为每个非空节点创建其左右子节点javapublic class CodecLevelOrder { // 序列化层序遍历二叉树 public String serialize(TreeNode root) { if (root null) return ; StringBuilder sb new StringBuilder(); QueueTreeNode 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); } // 移除末尾多余的分隔符 sb.setLength(sb.length() - 1); return sb.toString(); } // 反序列化根据层序序列重建树 public TreeNode deserialize(String data) { if (data null || data.isEmpty()) return null; String[] values data.split(,); if (values[0].equals(#)) return null; TreeNode root new TreeNode(Integer.parseInt(values[0])); QueueTreeNode queue new LinkedList(); queue.offer(root); int index 1; // 指向当前待处理子节点的数组位置 while (!queue.isEmpty() index values.length) { TreeNode parent queue.poll(); // 构建左子节点 if (index values.length !values[index].equals(#)) { parent.left new TreeNode(Integer.parseInt(values[index])); queue.offer(parent.left); } index; // 构建右子节点 if (index values.length !values[index].equals(#)) { parent.right new TreeNode(Integer.parseInt(values[index])); queue.offer(parent.right); } index; } return root; } }时间复杂度O(n)每个节点入队、出队各一次。空间复杂度O(n)队列中最多同时存储约n/2个节点完全二叉树的最后一层。二叉搜索树BST前序优化对于二叉搜索树BST可以利用其中序遍历为升序的特性仅通过前序或后序序列即可唯一确定树结构无需显式存储空节点。序列化思路对BST进行前序遍历将节点值拼接成字符串。由于BST的性质中序遍历就是节点值的升序排列因此仅凭前序遍历结果就能唯一确定树结构。反序列化思路根据前序遍历结果第一个元素为根节点。剩余元素中所有小于根节点的值构成左子树的前序遍历大于根节点的值构成右子树的前序遍历。递归进行即可重建BSTjavapublic 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 end preorder[rightStart] preorder[start]) { rightStart; } // 递归构建左子树和右子树 root.left buildBST(preorder, start 1, rightStart - 1); root.right buildBST(preorder, rightStart, end); return root; } }时间复杂度O(n log n) 最坏情况下BST退化为链表为O(n²)平均情况下为O(n log n)。这是因为在重建过程中需要为每个节点在序列中查找其左右子树的分界点。