这道题是经典的二叉树序列化问题利用 BST 的特性可以做到比通用二叉树更紧凑的编码。题目简述设计一个算法来序列化和反序列化二叉搜索树BST。序列化是将树转换为字符串反序列化是从字符串恢复原树。要求编码尽可能紧凑。核心思路序列化使用 前序遍历根-左-右将节点值用逗号分隔拼接成字符串。BST 的前序遍历有一个重要性质第一个值是根后面比根小的部分是左子树比根大的部分是右子树。反序列化将字符串按逗号分割成数组然后递归构建取第一个元素作为根节点。找到第一个大于根值的元素位置该位置之前是左子树的前序序列之后是右子树的前序序列。递归构建左右子树。Java 实现public class Codec {// 序列化前序遍历 public String serialize(TreeNode root) { if (root null) return ; StringBuilder sb new StringBuilder(); preorder(root, sb); return sb.toString(); } private void preorder(TreeNode node, StringBuilder sb) { if (node null) return; sb.append(node.val).append(,); preorder(node.left, sb); preorder(node.right, sb); } // 反序列化 public TreeNode deserialize(String data) { if (data null || data.isEmpty()) return null; String[] vals data.split(,); int[] index {0}; // 用数组包裹以便在递归中修改 return buildTree(vals, index, Integer.MIN_VALUE, Integer.MAX_VALUE); } private TreeNode buildTree(String[] vals, int[] index, int lower, int upper) { if (index[0] vals.length) return null; int val Integer.parseInt(vals[index[0]]); if (val lower || val upper) return null; index[0]; TreeNode node new TreeNode(val); node.left buildTree(vals, index, lower, val); // 左子树的值必须小于当前节点 node.right buildTree(vals, index, val, upper); // 右子树的值必须大于当前节点 return node; }}复杂度分析时间复杂度序列化 O(n)反序列化 O(n)每个节点只访问一次。空间复杂度O(n)递归栈深度最坏 O(n)退化为链表时平均 O(log n)。面试延伸为什么用前序遍历BST 的前序遍历 值域约束可以唯一确定一棵树无需像通用二叉树那样记录 null 节点。通用二叉树序列化通常用层序遍历或前序遍历 null 标记如 LeetCode 297。优化如果节点值范围已知可以用更紧凑的二进制编码而非字符串。需要我接着为你讲解 LeetCode 297. 二叉树的序列化与反序列化通用二叉树版本的对比实现吗
