297. 二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

思路

根据BNF的推导规则，即
<符号> ::= <使用符号的表达式>
二叉树可进行如下表示

  • 若当前的树空 ，则表示为X
  • 若当前的树非空，则表示为(<left_tree>) cur_num (<right_tree>)
    • left_tree和right_tree分别为左右子树序列化之后的结果
    • cur_num为当前节点值

故巴科斯范式如下：
S -> (S) num (S) | x
分析如下：

  • S（树序列化后的结果）的定义中，序列首字符为X或( ，右递归
  • 解析字符串时，若开头为X，则为空树，否则便解析(S) num (S)结构。无二义性

算法

  • 序列化方式：左子树->右子树->根节点
  • 反序列化:
    • 解析cur_num
    • 解析(S) num (S)

      实现

      ```cpp string recur_seri(TreeNode root){ if(!root) return ‘X’; return recur_seri(root->left)+to_string(root->val)+recur_seri(root->right); } string serialize(TreeNode root) { return recur_seri(root); }

// Decodes your encoded data to tree. TreeNode parse_num(string data,int& ptr){ ‘1000,-1000’ int x=0,sgn=1; if(!isdigit(data[ptr])){ sgn=-1; ptr++; } while(isdigit(data[ptr])){ x=x10+data[ptr++]-‘0’; } return x*sgn; }

TreeNode* parse_subtree(string data,int& ptr){ ++ptr; auto subtree=recur_deseri(data,ptr); ++ptr; return subtree;

} TreeNode recur_deseri(string data,int& ptr){ if(data[ptr]==’X’){ ++ptr; return nullptr; } auto cur=new TreeNode(0); cur->left = parse_subtree(data,ptr); cur->val = parse_num(data,ptr); cur->right = parse_subtree(data,ptr); return cur; } TreeNode deserialize(string data) { int ptr=0; return recur_deseri(data,ptr); } ```

复杂度分析

  • 时间复杂度:【例题】 - 图1
  • 空间复杂度:【例题】 - 图2