【Luogu】【关卡2-14】 树形数据结构（2017年10月）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <stack>
 5 #include <map>
 6 #include <vector>
 7 #include <string>
 8 
 9 using namespace std;
10 
11 void init(string& str) {
12     if (str.empty()) {
13         return;
14     }
15     if (str.size() == 1) {
16         if (str == "0") { cout << "B"; }
17         else if (str == "1") { cout << "I"; }
18         return;
19     }
20     string s1 = str.substr(0, str.size()/2);
21     string s2 = str.substr(str.size()/2);
22     init(s1);
23     init(s2);
24     if (str.find("0") != string::npos && str.find("1") != string::npos) {
25         cout << "F";
26     } else if (str.find("0") != string::npos) {
27         cout << "B";
28     } else {
29         cout << "I";
30     }
31     return;
32 }
33 
34 
35 int main() {
36     int n;
37     cin >> n;
38     string str;
39     cin >> str;
40     init(str);
41     cout << endl;
42     //system("pause");
43     return 0;
44 }

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <string>
 4 
 5 using namespace std;
 6 
 7 struct TreeNode {
 8     char val;
 9     TreeNode* left = nullptr;
10     TreeNode* right = nullptr;
11 };
12 
13 TreeNode* initTree(string& str1, string& str2) {
14     if  (str1.empty() && str2.empty()) {
15         return nullptr;
16     }
17     char c = str2[str2.size()-1];
18     TreeNode* root = new(TreeNode);
19     root->val = c;
20     int str1Pos = str1.find(c);
21     string str1Left = str1.substr(0, str1Pos);
22 
23     string str1Right = str1.substr(str1Pos + 1);
24 
25     string str2Left = str2.substr(0, str1Pos);
26 
27     string str2Right = str2.substr(str1Pos, str1Right.size());
28 
29     root->left = initTree(str1Left, str2Left);
30     root->right = initTree(str1Right, str2Right);
31     return root;
32 }
33 
34 string strans = "";
35 void visitTree(TreeNode* root) {
36     if (!root) { return; }
37     strans += root->val;
38     visitTree(root->left);
39     visitTree(root->right);
40     return;
41 }
42 
43 
44 int main() {
45     string s1, s2;
46     cin >> s1 >> s2;
47     TreeNode* root = initTree(s1, s2);
48     visitTree(root);
49     cout << strans << endl;
50     return 0;
51 }