[ABC255F] Pre-order and In-order Solution

• [ABC255F] Pre-order and In-order Solution
  • 更好的阅读体验戳此进入
  • 题面
  • Solution
  • Code
  • UPD

更好的阅读体验戳此进入

题面

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

Solution

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

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

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

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

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

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

using namespace std;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

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

int N;
int Pre[210000], In[210000];
int posP[210000], posI[210000];
pair < int, int > son[210000];

int dfs(int lp = 1, int rp = N, int li = 1, int ri = N){
    // printf("In dfs(%d ~ %d, %d ~ %d)\n", lp, rp, li, ri);
    if(lp > rp)return 0;
    int rt = Pre[lp];
    if(posI[rt] < li || posI[rt] > ri)puts("-1"), exit(0);
    if(lp == rp)return rt;
    int lsiz = (posI[rt] - 1) - li + 1;
    son[rt].first = dfs(lp + 1, lp + lsiz, li, posI[rt] - 1);
    son[rt].second = dfs(lp + lsiz + 1, rp, posI[rt] + 1, ri);
    return rt;
}

int main(){
    N = read();
    for(int i = 1; i <= N; ++i)posP[Pre[i] = read()] = i;
    for(int i = 1; i <= N; ++i)posI[In[i] = read()] = i;
    if(Pre[1] != 1)puts("-1"), exit(0);
    dfs();
    for(int i = 1; i <= N; ++i)printf("%d %d\n", son[i].first, son[i].second);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

update-2022_12_07 初稿