请实现两个函数，分别用来序列化和反序列化二叉树。
示例:
你可以将以下二叉树： 思路：序列化就是说根据某一种遍历算法把树的节点值存储起来，反序列化就是能够根据此存储的值重建二叉树，从官方题解这里给出的示例可以看出，用的是层次遍历，那我们也用层次遍历吧。
代码：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Codec { public: //使用string的流快很多 // Encodes a tree to a single string. string serialize(TreeNode* root) { ostringstream out; queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* tmp = q.front(); q.pop(); if (tmp != NULL)//如果是节点 { out<< tmp->val <<" ";//节点值+ " " q.push(tmp->left); q.push(tmp->right); } else { out<<"null"<<" ";//null + " " } } return out.str(); } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { istringstream input(data); string val; vector<TreeNode*> vec; while (input >> val) { if (val == "null") { vec.push_back(NULL); } else { vec.push_back(new TreeNode(stoi(val))); } } int j = 1; // i每往后移动一位，j移动两位，j始终是当前i的左子下标 for (int i = 0; j < vec.size(); ++i) // 肯定是j先到达边界，所以这里判断j < vec.size() { if (vec[i] == NULL) continue; // vec[i]为null时跳过。 if (j < vec.size()) vec[i]->left = vec[j++]; // 当前j位置为i的左子树 if (j < vec.size()) vec[i]->right = vec[j++]; // 当前j位置为i的右子树 } return vec[0]; } }; // Your Codec object will be instantiated and called as such: // Codec codec; // codec.deserialize(codec.serialize(root));直观一点的实现方法，但是时间和空间比上面那种高很多。（或许重建时采用数组索引快一些吧）
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Codec { public: //使用string的流快很多 // Encodes a tree to a single string. string serialize(TreeNode* root) { ostringstream out; queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* tmp = q.front(); q.pop(); if (tmp != NULL)//如果是节点 { out<< tmp->val <<" ";//节点值+ " " q.push(tmp->left); q.push(tmp->right); } else { out<<"null"<<" ";//null + " " } } return out.str(); } // Decodes your encoded data to tree. //利用队列按层构建二叉树 TreeNode* deserialize(string data) { TreeNode* ret = nullptr; queue<TreeNode*> q; istringstream input(data); string s; input >> s; if(s!="null") { ret = new TreeNode(stoi(s));//构建根节点 q.push(ret); while(!q.empty()) { TreeNode* front = q.front(); q.pop(); string left, right; input>>left>>right;//将左节点和右节点读取进来 if(left!="null") { front->left = new TreeNode(stoi(left));//将左孩子加入进来 q.push(front->left); } if(right!="null") { front->right = new TreeNode(stoi(right));//将右孩子加入进来 q.push(front->right); } } } return ret; } }; // Your Codec object will be instantiated and called as such: // Codec codec; // codec.deserialize(codec.serialize(root));