每日一题：二叉树遍历(flist) 4.3

每日一题：二叉树遍历(flist) 4.3

样例

输入数据 1

DBEAC
ABCDE

输出数据 1

ABDEC

分析：

1. 层次遍历的第一个结点一定是根节点

2. 先找到根节点，然后输出根节点，然后递归左子树、右子树

3. 先序遍历：根—>左—>右

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
string a, b;
int len, flag[1005];
void dg(int l, int r){int u, min =  0x3f3f3f3f;for(int k=l; k<=r; k++){	//	找根 if(flag[a[k]-'A'+ 1] < min){min = flag[a[k]-'A'+1];u = k;}}cout << a[u];//根 if(u > l) dg(l, u-1);//递归左子树 if(u < r) dg(u+1, r);//递归右子树 
}
int main(){cin >> a >> b;len = b.size();for(int i=0; i<len; i++){    // 在层次遍历中记录每个结点的下标flag[b[i]-'A'+1] = i;}dg(0, a.size()-1);return 0;
}