题解
观察层序遍历可知,我们得到以下结论:
1. 层序遍历输出的第一个节点一定是根节点
2. 中序遍历中当前结点一定是中序遍历[l2, r2]
的结点在层次遍历中最靠前的位置
所以,我们每次用循环来寻找根,也就是[l2, r2]
的最靠前的位置,然后递归重复操作即可。
#include <bits/stdc++.h>
using namespace std;
string InOrder, LevelOrder;
void getPreOder(int l1, int r1, int l2, int r2) {
int i, j;
for(i = l2; i <= r2; i++) {
bool flag = false;
for(j = l1; j <= r1; j++) {
if(LevelOrder[i] == InOrder[j]) {
cout << LevelOrder[i];
flag = true;
break;
}
}
if(flag) break;
}
if(j > l1) getPreOder(l1, j - 1, 0, r2);
if(j < r1) getPreOder(j + 1, r1, 0, r2);
}
int main() {
cin >> InOrder >> LevelOrder;
getPreOder(0, InOrder.size() - 1, 0, LevelOrder.size() - 1);
return 0;
}
递归时
l2
不需要每次都从0
开始:数据太小图省事就直接0开始了😂
这种写法很巧妙,需要想些时间才能理解,但是比较简洁,
不知道 前+中 的组合是否可以用类似简洁的代码解出?