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

subject ： 

Topic link ： F - Pre-order and In-order (atcoder.jp)

---

Answer key ：Editorial - Aising Programming Contest 2022（AtCoder Beginner Contest 255）

---

  Ideas : 

Because the official explanation has made it very clear

Here I will briefly add some

1. First of all, we need to understand pre-order（ Preface ） and in-order（ Middle preface ） The concept of  

2. Because what we want to build is a binary tree that meets the determination of the preorder and the middle order in the topic

I can build L[10006] and R[10006] Array of

Store separately L[i] and R[i] Left node and right node of

3. When constructing an edge, judge whether it meets the preorder and middle order

It is mainly to judge whether the node is out of bounds

---

Code details ：

#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 For in p The scope of ,S,E For in i The scope of 
	int root = P[s], p = Iinv[root];//p Is the position in the sequence 
	if (p<S || p>E) return 0;// The node is not within the scope of the constructed subtree 

	if (p - S > 0) {// Able to build left subtree 
		L[root] = P[s + 1];// With p in s+1 As the root node of the subtree , And recorded in L in 
		if (!slove(s + 1, e, S, p - 1)) return 0;
		// to update [S,P-1] As the new subtree interval range , to update [s+1,e] As 
	}
	if (E - p > 0) {// ditto 
		R[root] = P[s+p-S+1];//p The first of the right child nodes in 
		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 Must act as root
		cout << -1 << endl;
		return 0;
	}
	
	for (int i = 1; i <= n; i++) cout << L[i] << " " << R[i]<<endl;
	return 0;
}