F - Pre-order and In-order（Atcoder 255）

题目： 

题目链接： F - Pre-order and In-order (atcoder.jp)

---

题解：Editorial - Aising Programming Contest 2022（AtCoder Beginner Contest 255）

---

 思路: 

因为官方题解已经说的很清楚了

我这里就简要补充一些

1.首先大家要了解pre-order（先序）和in-order（中序）的概念 

2.因为要构建的为一个满足题目中先序和中序确定的一个二叉树

我可以通过一个构建L[10006]和R[10006]的数组

分别存储L[i]和R[i]的左结点和右结点

3.边构造的时候边判断是否满足先序和中序

主要是判断是否结点越界的问题

---

代码详解：

#include<iostream>
using namespace std;
const int N = 200006;
int P[N], I[N], Iinv[N];
int L[N], R[N];
bool slove(int s,int e,int S,int E) {//s,e为在p中的范围，S,E为在i中的范围
	int root = P[s], p = Iinv[root];//p为在中序列的位置
	if (p<S || p>E) return 0;//结点不在构建的子树范围内

	if (p - S > 0) {//能够构建左子树
		L[root] = P[s + 1];//以p中s+1作为子树的根结点，并记录在L中
		if (!slove(s + 1, e, S, p - 1)) return 0;
		//更新[S,P-1]为作为新子树区间范围，更新[s+1,e]作为
	}
	if (E - p > 0) {//同上
		R[root] = P[s+p-S+1];//p中的右子结点的第一个
		if (!slove(s + p - S + 1, e, p + 1, E)) return 0;
	}

	return 1;
}
int main(){
	int n;
	cin >> n;
	for (int i = 1; i <=n; i++) cin >> P[i];
	for (int i = 1; i <=n; i++) cin >> I[i];
	for (int i = 1; i <=n; i++) Iinv[I[i]]=i;

	if (P[1] != 1 || !slove(1, n, 1, n)) {//1必须作为root
		cout << -1 << endl;
		return 0;
	}
	
	for (int i = 1; i <= n; i++) cout << L[i] << " " << R[i]<<endl;
	return 0;
}