[ABC255F] Pre-order and In-order Solution

更好的阅读体验戳此进入

题面

给定一棵二叉树的先序遍历和中序遍历，请构造一棵以 $1$$1$ 节点为根的二叉树。第 $i$$i$ 行输出节点 $i$$i$ 的左右儿子，儿子为空则输出 $0$$0$。无解输出 -1。

Solution

也是一道水题，考虑先序和中序的意义即可。

众所周知，先序遍历的顺序是根、左子树、右子树。中序遍历是左子树、根、右子树。

于是不难发现，在当前的先序遍历中取第一个数即为当前的根，然后在中序遍历中找到根的位置，其左侧即为整个左子树，右侧为整个右子树。于是不难想到 dfs 即可，参数维护当前的整个子树属于先序遍历的 $[lp,rp]$$[lp, rp]$，属于中序遍历的 $[li,ri]$$[li, ri]$，然后需要记录每个数的位置，通过中序遍历根和左右之间的数的个数，可计算左右子树的大小，以此即可确定先序遍历左右子树的下一个区间，以此递归下去即可。

考虑无解的情况，要么先序遍历的第一个值不为 $1$$1$，说明二叉树根不为 $1$$1$。要么就是在递归过程中，确定先序的第一位为根之后，根在中序中的位置超出了当前的限制位置，在这两种特殊情况记录一下无解即可。

Code

xxxxxxxxxx
67
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
int N;
26
int Pre[210000], In[210000];
27
int posP[210000], posI[210000];
28
pair < int, int > son[210000];
29

30
int 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

42
int 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

53
template < typename T >
54
inline 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
}

UPD

update-2022_12_07 初稿