Careercup

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.

题目：给定一棵二叉树，请设计序列化和反序列化的方法。

解法：我的方法是使用前序遍历来进行序列化，其中大括号"{}"包含了数据序列，用“#”表示空指针。反序列化的思路则相反。

代码：

 1 // http://www.careercup.com/question?id=5729456584916992
 2 #include <cstdio>
 3 #include <string>
 4 #include <vector>
 5 using namespace std;
 6 
 7 struct TreeNode {
 8     int val;
 9     TreeNode *left;
10     TreeNode *right;
11     TreeNode(int _val = 0): val(_val), left(nullptr), right(nullptr) {};
12 };
13 
14 class BinaryTreeSerializer {
15 public:
16     string serialize(TreeNode *root) {
17         string res = "{";
18         
19         // preorder traversal
20         serializeTraversal(root, res);
21         res[res.length() - 1] = '}';
22         
23         return res;
24     };
25     
26     TreeNode *deserialize(string s) {
27         vector<string> data;
28         int i, j, len;
29         
30         len = (int)s.length();
31         i = 1;
32         while (true) {
33             j = i + 1;
34             while (s[j] != ',' && s[j] != '}') {
35                 ++j;
36             }
37             data.push_back(s.substr(i, j - i));
38             i = j + 1;
39             if (i >= len) {
40                 break;
41             }
42         }
43         
44         int iter = 0;
45         TreeNode *root = nullptr;
46         
47         // preorder traversal
48         deserializeTraversal(data, root, iter);
49         
50         return root;
51     };
52 private:
53     static char ss[10];
54     
55     void serializeTraversal(TreeNode *root, string &res) {
56         if (root == nullptr) {
57             res += "#,";
58         } else {
59             sprintf(ss, "%d", root->val);
60             res += string(ss);
61             res.push_back(',');
62             serializeTraversal(root->left, res);
63             serializeTraversal(root->right, res);
64         }
65     };
66     
67     void deserializeTraversal(vector<string> &data, TreeNode *&root, int &iter) {
68         ++iter;
69         if (data[iter - 1] == "#") {
70             root = nullptr;
71         } else {
72             int val;
73             
74             sscanf(data[iter - 1].c_str(), "%d", &val);
75             root = new TreeNode(val);
76             deserializeTraversal(data, root->left, iter);
77             deserializeTraversal(data, root->right, iter);
78         }
79     };
80 };