题面
请实现两个函数,分别用来序列化和反序列化二叉树。
示例
1 2 3 4 5 6 7 8 9
| 你可以将以下二叉树:
1 / \ 2 3 / \ 4 5
序列化为 "[1,2,3,null,null,4,5]"
|
思路
BFS层序遍历即可,注意,如果节点为null,则它的子节点就不记录。
即
表示为[1,null,2,3] 而非[1,null,2,null,null,3]
反序列化时不能使用父子节点的下标关系。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
|
class Codec { public:
string serialize(TreeNode* root) { if(root == nullptr) return "[]"; string res = "["; queue<TreeNode *> q; q.push(root); while(!q.empty()){ TreeNode *t = q.front(); q.pop(); if(t == nullptr){ res += "null,"; }else{ res += to_string(t->val) + ","; q.push(t->left); q.push(t->right); } } res[res.length()-1] = ']'; return res; }
TreeNode* deserialize(string data) { if(data=="[]") return nullptr; vector<TreeNode *> v; for(int i=0; i<data.length(); i++){ if(data[i]=='-' || isdigit(data[i])){ int f=1, x=0; if(data[i]=='-'){ f = -1; i++; } for(; isdigit(data[i]); i++){ x = x*10 + (data[i]-'0'); } i--; x *= f; TreeNode *p = new TreeNode(x); v.push_back(p); }else if(data[i]=='n'){ v.push_back(nullptr); i += 3; } } for(int i=0, j=1; i<v.size()&&j<v.size(); i++,j++){ while(v[i]==nullptr) i++; v[i]->left = v[j++]; v[i]->right = v[j]; } return v[0]; } };
|