Careercup

2014-05-12 07:17

原题：

Given below is a tree/trie 
A 
B    c D 
e    F 
a<b<e<>>c<>d<f<>>> 
above string represents the following trie/tree (visualize) and assume that there exisits a serialize method that performs above. 
Now, write a deserialize method so that above string to an object model of the following 
TreeNode 
TreeNode[] children

题目：给定以上的字典树序列化方法，请写出相应的反序列化方法。

解法：观察序列化的字符串，可以发现序列化的规则是“字母<若干个子树>”。用一个栈就可以写出比较简洁的反序列化代码。

代码：

 1 // http://www.careercup.com/question?id=5799446021406720
 2 #include <iostream>
 3 #include <stack>
 4 #include <string>
 5 #include <vector>
 6 using namespace std;
 7 
 8 struct TrieNode {
 9     char ch;
10     vector<TrieNode *> child;
11     TrieNode(char _ch = 0): ch(_ch), child(vector<TrieNode *>()) {};
12 };
13 
14 TrieNode *deserializeFromString(const string &str)
15 {
16     TrieNode *root;
17     TrieNode *ptr;
18     stack<TrieNode *>  st;
19     
20     int i, n;
21     
22     root = nullptr;
23     n = (int)str.length();
24     i = 0;
25     while (i < n) {
26         if (str[i] == '>') {
27             st.pop();
28             ++i;
29         } else {
30             ptr = new TrieNode(str[i]);
31             i += 2;
32             if (st.empty()) {
33                 root = ptr;
34             } else {
35                 (st.top()->child).push_back(ptr);
36             }
37             st.push(ptr);
38         }
39     }
40     
41     return root;
42 }
43 
44 void preorderTraversal(TrieNode *root)
45 {
46     if (root == nullptr) {
47         return;
48     }
49     cout << root->ch << ' ';
50     for (int i = 0; i < (int)root->child.size(); ++i) {
51         preorderTraversal(root->child[i]);
52     }
53 }
54 
55 int main()
56 {
57     TrieNode *root = nullptr;
58     string str;
59     
60     while (cin >> str) {
61         root = deserializeFromString(str);
62         preorderTraversal(root);
63         cout << endl;
64     }
65     
66     return 0;
67 }