剑指offer 序列化二叉树

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };
10 */
11 class Solution {
12 public:
13     char* Serialize(TreeNode *root)
14     {
15         string s;
16         queue<TreeNode*> qt;
17         qt.push(root);
18         while (!qt.empty()) {
19             // pop operator
20             TreeNode *node = qt.front();
21             qt.pop();
22             // process null node
23             if (node == nullptr) {
24                 s.push_back(‘#‘);
25                 s.push_back(‘!‘);
26                 continue;
27             }
28             // process not null node
29             s += to_string(node->val);
30             s.push_back(‘!‘);
31             // push operator
32             qt.push(node->left);
33             qt.push(node->right);
34         }
35         char *ret = new char[s.length() + 1];
36         strcpy(ret, s.c_str());
37         return ret;
38     }
39     TreeNode* Deserialize(char *str) {
40         if (str == nullptr) {
41             return nullptr;
42         }
43         // 可用string成员函数
44         string s(str);
45         if (str[0] == ‘#‘) {
46             return nullptr;
47         }
48         // 构造头结点
49         queue<TreeNode*> nodes;
50         TreeNode *ret = new TreeNode(atoi(s.c_str()));
51         s = s.substr(s.find_first_of(‘!‘) + 1);
52         nodes.push(ret);
53         // 根据序列化字符串再层次遍历一遍，来构造树
54         while (!nodes.empty() && !s.empty())
55         {
56             TreeNode *node = nodes.front();
57             nodes.pop();
58             if (s[0] == ‘#‘)
59             {
60                 node->left = nullptr;
61                 s = s.substr(2);
62             }
63             else
64             {
65                 node->left = new TreeNode(atoi(s.c_str()));
66                 nodes.push(node->left);
67                 s = s.substr(s.find_first_of(‘!‘) + 1);
68             }
69             if (s[0] == ‘#‘) {
70                 node->right = nullptr;
71                 s = s.substr(2);
72             }
73             else {
74                 node->right = new TreeNode(atoi(s.c_str()));
75                 nodes.push(node->right);
76                 s = s.substr(s.find_first_of(‘!‘) + 1);
77             }
78         }
79         return ret;
80     }
81 };