ABC255F

想不到我一个pj2=的人也能做出F题啊！

注：我以前看不懂EF的Editorial，所以从没做出来过……

题面

给你一棵二叉树的前序和中序遍历，重构这颗二叉树。（根节点为1）

Part1 确定根节点和左右子树的所有节点

谁都知道一颗二叉树的根节点就是它的前序遍历的第一项。
那么确定左右子树的内容就交给中序遍历了。
$ pre_1 $ $ pre_2 $ $ pre_3 $ 根节点： $ pre_1 $

$ in_1 $ $ in_2 $ $ in_3 $ 发现 $ pre_1 = in_2 $，可以确定左子树与右子树。

Part2 确定左子树根节点和左右子树的所有节点

请重新阅读 Part1。

Part3 Error!

如果我们确定到的根节点不在递归范围之内，那就对不住了！

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

#define maxn 200005

int L[maxn], R[maxn];
int pre[maxn], in[maxn], inv[maxn];

bool solve(int preL, int preR, int inL, int inR) { // 递归范围：前序preL ~ preR，中序inL ~ inR
	int Rt = pre[preL], invRt = inv[Rt]; // 根和根在中序里的位置
	if (inL > invRt || invRt > inR) { // Part3
		return false;
	}
	if (invRt - inL > 0) {
		L[Rt] = pre[preL + 1];
		if (!solve(preL + 1, preL + invRt - inL, inL, invRt - 1)) { // Part2，长度为invRt - inL
			return false;
		}
	}
	if (inR - invRt > 0) {
		R[Rt] = pre[preL + invRt - inL + 1];
		if (!solve(preL + invRt - inL + 1, preR, invRt + 1, inR)) { // Part2 Again
			return false;
		}
	}
	return true;
}

int main() {
	memset(L, -1, sizeof(L));
	memset(R, -1, sizeof(R));
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &pre[i]);
		pre[i]--;
	}
	for (int i = 0; i < n; i++) {
		scanf("%d", &in[i]);
		in[i]--;
		inv[in[i]] = i; // 预处理出节点在中序里的位置
	}
	if (pre[0] != 0 || !solve(0, n - 1, 0, n - 1)) { // Part1 + Part3
		printf("%d", -1); // Part3
	} else {
		for (int i = 0; i < n; i++) {
			printf("%d %d\n", L[i] + 1, R[i] + 1); // 注意！我用的是0 ~ n - 1，题目是1 ~ n！
		}
	}
	return 0;
}

后记

马上要到暑假啦 ~
暑假会一周4 ~ 7更！
P.S. 祝大家今晚的Atcoder RP++！

都看到这里了，还不点赞推荐加关注 ~
不白嫖，从我做起！

题解

相关

洛谷P5340 大中锋的游乐场 题解 分层图最短路

Ubuntu 断网问题解决

[SQL] SQL Server 2019 中LocalDB 报错的问题解决

题解 Count on a tree II/【模板】树分块

HttpURLConnection发送中文乱码问题解决

1675: [Usaco2005 Feb]Rigging the Bovine Election 竞选划区（题解第一弹）

P7715 「EZEC-10」Shape 题解

Proguard混淆之后行数LineNumber对不上问题解决

ZYNQ xilinx_axienet CPU软中断占用过高问题解决记录

题解 P6345 [CCO 2017]接雨滴

魔咒词典 - 题解【暴搜】

最大数maxnumber - 题解【树状数组】

标签