题目描述
观察层序遍历可知,我们得到以下结论:
1. 层序遍历输出的第一个节点一定是根节点
2. 中序遍历中当前结点一定是中序遍历[l2, r2]的结点在层次遍历中最靠前的位置
所以,我们每次用循环来寻找根,也就是[l2, r2]的最靠前的位置,然后递归重复操作即可。
样例
blablabla
算法1
(dfs) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 30;
int len;
char a[N],b[N];
void preorder(int left, int right)
{
int i, j;
bool flag = false;
for(i = 0; i < len; i ++)
{
for(j = left; j <= right; j ++ )
{
if(b[i] == a[j])
{
cout << a[j];
flag = 1;
break;
}
}
if(flag) break;
}
if(left < j) preorder(left, j - 1);
if(j < right) preorder(j + 1, right);
}
int main()
{
cin >> a >> b;
len = strlen(a);
preorder(0, len - 1);
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla