原题链接
解题思路
利用前序遍历和中序遍历的特点进行深搜
深搜退出条件：中序首>=尾不成立
深搜递归：改变根节点，中序首尾指向，存放下标
要点：由前序找到中序的根
ac代码
#include <iostream>
#include <cstring>
using namespace std;
int in[30], pre[30];
int level[100000];//数组要开大一点，因为不是完全二叉树
void dfs(int root, int start, int end, int index) {
//root前序遍历的首 start,end中序遍历的首尾 index存放的下标
if(start > end) return;
level[index] = pre[root];//此（子）树的根节点，储存
int i = start;
while(i < end && in[i] != pre[root]) i++;//找到中序遍历中的根节点 （这也是前序遍历的左右子树分开点）
dfs(root + 1, start, i - 1, 2 * index + 2);//这里巧妙的将结点换位置，将左边和右边结点换位置。
dfs(root + (i - start) + 1, i + 1, end, 2 * index + 1);
}
int main() {
memset(level, -1, sizeof(level));
int n;
scanf("%d",&n);
for(int i = 0; i < n; i++) scanf("%d", &in[i]);
for(int i = 0; i < n; i++) scanf("%d", &pre[i]);
dfs(0, 0, n - 1, 0);
int cnt = 0;
for(int i = 0; i < 10000; i++) {
if(level[i] != -1) {
if(cnt != n - 1) {
printf("%d ", level[i]);
cnt++;
} else{
printf("%d", level[i]);
break;
}
}
}
return 0;
}
