LC.297 ｜ 二叉树的序列化与反序列化 ｜ 树 ｜ 定长编码传递信息

输入：二叉树的根节点root。

要求：设计一个算法，将二叉树序列化为一个字符串，并且可以将该字符串反序列化为原始的树结构。不限制具体的序列化逻辑（如前序、层序等），只要保证“编码 -> 解码”过程可逆且准确即可。

输出：

• serialize: 返回编码后的string。
• deserialize: 返回还原后的TreeNode*。

本题很有意思，序列化与反序列化，然后全程只有一个字符串传递，之前我们已经做到简单版的问题，这一题一部分难点在于如何用string传递足够多的信息，颇有点计算机的本质了，就是信息的传递。
采用了一种自定义的“定长编码协议”结合 BFS 来实现，避免了复杂的字符串分割操作。

1. 序列化 (Serialize) - 定长编码规则：

   • 使用层序遍历 (BFS)。
   • 不使用分隔符（如逗号），而是将每个节点的信息固定编码为7个字符的字符串片段。
   • 格式定义：[符号位 1位][数值位 4位][左孩子存在标志 1位][右孩子存在标志 1位]。
     • 第1位：符号。0表示正数，1表示负数。
     • 第2-5位：数值的绝对值，不足4位前面补0（已知数值范围在 -1000 到 1000 之间）。
     • 第6位：左孩子标记。1表示有左孩子，0表示无。
     • 第7位：右孩子标记。1表示有右孩子，0表示无。
   • 遍历过程中，如果孩子存在，将其入队，并在当前节点的字符串中标记为1；否则标记0且不记录空节点的数据。

2. 反序列化 (Deserialize) - 双指针索引法：

   • 同样利用队列进行 BFS 重建。
   • 维护两个索引（模拟指针）：
     • Idx：指向当前正在处理的父节点在字符串中的位置索引（第几个节点）。
     • Cur：指向字符串中下一个待分配的数据块的位置索引。
   • 流程：
     1. 先解析前7个字符构建根节点，入队。
     2. 当队列不为空时，取出队头节点（对应Idx指向的数据块）。
     3. 读取Idx数据块的第6位和第7位（左右孩子标记）。
     4. 如果标记为1，则从Cur指向的位置读取7个字符，构建子节点，连接到父节点，子节点入队，并让Cur加 1。
     5. 处理完当前节点后，Idx加 1。

复杂度：

• 时间复杂度：O(N)
  • 序列化和反序列化都需要遍历树中所有的节点一次。
• 空间复杂度：O(N)
  • 需要使用队列进行层序遍历，队列最大长度为树的一层节点数。同时需要存储序列化后的字符串，长度与节点数成正比。

classCodec{public:// Encodes a tree to a single string.stringserialize(TreeNode*root){if(!root)return"";queue<TreeNode*>q;string ser="";q.push(root);while(!q.empty()){intn=q.size();for(inti=0;i<n;i++){TreeNode*t=q.front();q.pop();if(t->val>=0){ser+="0";}else{ser+="1";}string valStr=to_string(abs(t->val));while(valStr.length()<4){valStr="0"+valStr;}ser+=valStr;if(t->left!=nullptr){ser+="1";q.push(t->left);}else{ser+="0";}if(t->right!=nullptr){ser+="1";q.push(t->right);}else{ser+="0";}}}returnser;}TreeNode*deserialize(string data){if(data==""){returnnullptr;}introotVal=(data[1]-'0')*1000+(data[2]-'0')*100+(data[3]-'0')*10+(data[4]-'0');if(data[0]=='1'){rootVal=-rootVal;}TreeNode*root=newTreeNode(rootVal);queue<TreeNode*>q;q.push(root);intCur=1;intIdx=0;while(!q.empty()){intn=q.size();for(inti=0;i<n;i++){TreeNode*t=q.front();q.pop();if(data[Idx*7+5]=='1'){intleftVal=(data[Cur*7+1]-'0')*1000+(data[Cur*7+2]-'0')*100+(data[Cur*7+3]-'0')*10+(data[Cur*7+4]-'0');if(data[Cur*7]=='1'){leftVal=-leftVal;}TreeNode*tmp=newTreeNode(leftVal);t->left=tmp;q.push(tmp);Cur++;}if(data[Idx*7+6]=='1'){intrightVal=(data[Cur*7+1]-'0')*1000+(data[Cur*7+2]-'0')*100+(data[Cur*7+3]-'0')*10+(data[Cur*7+4]-'0');if(data[Cur*7]=='1'){rightVal=-rightVal;}TreeNode*tmp=newTreeNode(rightVal);t->right=tmp;q.push(tmp);Cur++;}Idx++;}}returnroot;}};