给定一棵二叉树的先序遍历和中序遍历,请构造一棵以 -1
。
也是一道水题,考虑先序和中序的意义即可。
众所周知,先序遍历的顺序是根、左子树、右子树。中序遍历是左子树、根、右子树。
于是不难发现,在当前的先序遍历中取第一个数即为当前的根,然后在中序遍历中找到根的位置,其左侧即为整个左子树,右侧为整个右子树。于是不难想到 dfs 即可,参数维护当前的整个子树属于先序遍历的
考虑无解的情况,要么先序遍历的第一个值不为
xxxxxxxxxx
671
2
3
4
5
6
7
8
9
10
11using namespace std;
12
13mt19937 rnd(random_device{}());
14int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15bool rnddd(int x){return rndd(1, 100) <= x;}
16
17typedef unsigned int uint;
18typedef unsigned long long unll;
19typedef long long ll;
20typedef long double ld;
21
22template < typename T = int >
23inline T read(void);
24
25int N;
26int Pre[210000], In[210000];
27int posP[210000], posI[210000];
28pair < int, int > son[210000];
29
30int dfs(int lp = 1, int rp = N, int li = 1, int ri = N){
31 // printf("In dfs(%d ~ %d, %d ~ %d)\n", lp, rp, li, ri);
32 if(lp > rp)return 0;
33 int rt = Pre[lp];
34 if(posI[rt] < li || posI[rt] > ri)puts("-1"), exit(0);
35 if(lp == rp)return rt;
36 int lsiz = (posI[rt] - 1) - li + 1;
37 son[rt].first = dfs(lp + 1, lp + lsiz, li, posI[rt] - 1);
38 son[rt].second = dfs(lp + lsiz + 1, rp, posI[rt] + 1, ri);
39 return rt;
40}
41
42int main(){
43 N = read();
44 for(int i = 1; i <= N; ++i)posP[Pre[i] = read()] = i;
45 for(int i = 1; i <= N; ++i)posI[In[i] = read()] = i;
46 if(Pre[1] != 1)puts("-1"), exit(0);
47 dfs();
48 for(int i = 1; i <= N; ++i)printf("%d %d\n", son[i].first, son[i].second);
49 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
50 return 0;
51}
52
53template < typename T >
54inline T read(void){
55 T ret(0);
56 int flag(1);
57 char c = getchar();
58 while(c != '-' && !isdigit(c))c = getchar();
59 if(c == '-')flag = -1, c = getchar();
60 while(isdigit(c)){
61 ret *= 10;
62 ret += int(c - '0');
63 c = getchar();
64 }
65 ret *= flag;
66 return ret;
67}
update-2022_12_07 初稿