sicily 1935 二叉树重建

Description

对于二叉树T，可以递归定义它的先序遍历、中序遍历和后序遍历如下： PreOrder(T)=T的根节点+PreOrder(T的左子树)+PreOrder(T的右子树) InOrder(T)=InOrder(T的左子树)+T的根节点+InOrder(T的右子树) PostOrder(T)=PostOrder(T的左子树)+PostOrder(T的右子树)+T的根节点其中加号表示字符串连接运算。例如，对下图所示的二叉树，先序遍历为DBACEGF，中序遍历为ABCDEFG。
输入一棵二叉树的先序遍历序列和中序遍历序列，输出它的广度优先遍历序列。

Input

第一行为一个整数t（0<t<10），表示测试用例个数。以下t行，每行输入一个测试用例，包含两个字符序列s1和s2，其中s1为一棵二叉树的先序遍历序列，s2为中序遍历序列。s1和s2之间用一个空格分隔。序列只包含大写字母，并且每个字母最多只会出现一次。

Output

为每个测试用例单独一行输出广度优先遍历序列。

Sample Input

2 
DBACEGF ABCDEFG 
BCAD CBAD

Sample Output

DBEACGF 
BCAD

分析：

本题很直白，就是知道二叉树前序和中序遍历的结果，然后输出广度优先遍历的结果。明白二叉树遍历的递归方式就能很明白的看出解法。

对于每棵树或者子树，他的前序和中序遍历序列都有特定的性质，即前序序列开始的节点一定是根节点。那么中序序列中次节点将序列分城左右两个子序列，分别对应左右子树中序遍历结果。如此左右子树节点数目已知，那么就可以在前序序列中找出左右子树前序遍历结果，这样递归处理就能还原二叉树，然后调用BSF方法即可。

PS：二叉树处理方法大都与递归相关，而且递归的中心在于树或者子树的根，牢牢抓住至一点就能化繁为简。另外，其实前序遍历算是广度优先遍历。

代码：

 1 // Problem#: 1935
 2 // Submission#: 1895987
 3 // The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
 4 // URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
 5 // All Copyright reserved by Informatic Lab of Sun Yat-sen University
 6 #include <iostream>
 7 #include <string>
 8 #include <queue>
 9 using namespace std;
10 
11 struct node{
12     char left;
13     char right;
14 }buffer[30];
15 
16 void tree(string str1, string str2) {
17     int size = str1.size();
18     if (size == 0) return ;
19     int a = str2.find(str1[0]);
20     int b = str1[0] - 'A';
21     string l1, l2, r1, r2;
22     l1 = a ? str1.substr(1, a): "";
23     l2 = a ? str2.substr(0, a): "";
24     r1 = (a < size - 1) ? str1.substr(a + 1, size - 1 - a): "";
25     r2 = (a < size - 1) ? str2.substr(a + 1, size - 1 - a): "";
26     buffer[b].left = a ? l1[0] : '\0';
27     buffer[b].right = (a < size - 1) ? r1[0] : '\0';
28     tree(l1, l2);
29     tree(r1, r2);
30 }
31 
32 void bfs(char c) {
33     queue<char> tmp;
34     tmp.push(c);
35     while (!tmp.empty()) {
36         char t = tmp.front();
37         cout << t;
38         tmp.pop();
39         node n = buffer[t - 'A'];
40         if (n.left != '\0') tmp.push(n.left);
41         if (n.right != '\0') tmp.push(n.right);
42     }
43 }
44 
45 int main() {
46     int t;
47     string preOrder, inOrder;
48     cin >> t;
49     while (t--) {
50         cin >> preOrder >> inOrder;
51         tree(preOrder, inOrder);
52         bfs(preOrder[0]);
53         cout << endl;
54     }
55     return 0;
56 }