正文
Careercup - Facebook面试题 - 5729456584916992
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
2014-05-02 00:59
题目链接
原题：
Given a normal binary tree, write a function to serialize the tree into a string representation (returning the string), and also a function to deserialize a serialized string into the original binary tree.
题目：给定一棵二叉树，请设计序列化和反序列化的方法。
解法：我的方法是使用前序遍历来进行序列化，其中大括号"{}"包含了数据序列，用“#”表示空指针。反序列化的思路则相反。
代码：
// http://www.careercup.com/question?id=5729456584916992
#include <cstdio>
#include <string>
#include <vector>
using namespace std; struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int _val = ): val(_val), left(nullptr), right(nullptr) {};
}; class BinaryTreeSerializer {
public:
string serialize(TreeNode *root) {
string res = "{"; // preorder traversal
serializeTraversal(root, res);
res[res.length() - ] = '}'; return res;
}; TreeNode *deserialize(string s) {
vector<string> data;
int i, j, len; len = (int)s.length();
i = ;
while (true) {
j = i + ;
while (s[j] != ',' && s[j] != '}') {
++j;
}
data.push_back(s.substr(i, j - i));
i = j + ;
if (i >= len) {
break;
}
} int iter = ;
TreeNode *root = nullptr; // preorder traversal
deserializeTraversal(data, root, iter); return root;
};
private:
static char ss[]; void serializeTraversal(TreeNode *root, string &res) {
if (root == nullptr) {
res += "#,";
} else {
sprintf(ss, "%d", root->val);
res += string(ss);
res.push_back(',');
serializeTraversal(root->left, res);
serializeTraversal(root->right, res);
}
}; void deserializeTraversal(vector<string> &data, TreeNode *&root, int &iter) {
++iter;
if (data[iter - ] == "#") {
root = nullptr;
} else {
int val; sscanf(data[iter - ].c_str(), "%d", &val);
root = new TreeNode(val);
deserializeTraversal(data, root->left, iter);
deserializeTraversal(data, root->right, iter);
}
};
};
