Znzryb's Blog
0%

力扣 105. 从前序与中序遍历序列构造二叉树 天梯赛选拔赛L2-1 种树（知道先序排列和中序排列，求二叉树结构）

Posted on Edited on

image

L2-1 种树

https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

以先序 [1, 2, 4, 5, 3, 6]、中序 [4, 2, 5, 1, 3, 6] 为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
先序第一个 = 1（根）
在中序中找到 1 的位置，左边 [4,2,5]（3个），右边 [3,6]（2个）

          1
         / \
  左子树    右子树
  先序[2,4,5] 先序[3,6]
  中序[4,2,5] 中序[3,6]

继续递归左子树：根=2，中序中 2 左边[4]，右边[5]
继续递归右子树：根=3，中序中 3 左边空，右边[6]

最终：
          1
         / \
        2   3
       / \   \
      4   5   6

红色代表第一次（递归），蓝色代表第二次，黄色代表第三次。

image

应该算是一道典题了，但是问题在于我上次做这道题目还是在上次~~（刚学的时候，还是在用python那）~~

总体来讲，就是利用先序的root->left->right，中序的left->root->right，递归求解二叉树结构。

应该是没有太大问题的，比标程还多在我的电脑上过了一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
// http://120.55.170.42/contest/1001/problem/L2-1
#include <bits/stdc++.h>
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T,Pre[MAXN],Mid[MAXN];
map<ll,ll> posP,posM;
pll ans[MAXN];
// 根以及区域(在先序遍历上的范围)（因为只有在这个范围内先序root才是对的）
// ml,mr就是中序排列范围
bool flag=false;
void dfs(ll root,ll l,ll r,ll ml,ll mr){
	if(r<=l){
		return;
	}
	if(mr<=ml){
		return;
	}
	if(flag) return;
	ll rootm=posM[root];
	if(rootm<ml || rootm>mr){
		flag=true;
		return;
	}
	ll weiL=rootm-ml,weiR=mr-rootm;
	ll rootl=0,rootr=0;
// #ifdef LOCAL
    // cerr << root << " "<< l<<" "<<r<<" "<<weiL<<" "<<weiR << '\n';
// #endif
	if(/*l+1<=r &&*/ weiL>1){
		rootl=Pre[l+1];
		dfs(rootl,l+1,l+weiL,ml,rootm-1);
	}else if(weiL==1){
		rootl=Pre[l+1];
	}
	if(/*l+weiL+1<=r &&*/ weiR>1){
		rootr=Pre[l+weiL+1];
		dfs(rootr,l+weiL+1,r,rootm+1,mr);
	}else if(weiR==1){
		rootr=Pre[l+weiL+1];
	}
	ans[root].fi=rootl;
	ans[root].se=rootr;
}

inline void solve(){
	cin>>N;
	for(int i=1;i<=N;++i){
		cin>>Pre[i];
		posP[Pre[i]]=i;
	}
	for(int i=1;i<=N;++i){
		cin>>Mid[i];
		posM[Mid[i]]=i;
	}
	for(int i=1;i<=N;++i){	// 初始化
		ans[i].fi=0;
		ans[i].se=0;	
	}
	flag=false;
	dfs(1,1,N,1,N);
	if(flag){
		cout<<-1<<"\n";
		return;
	}
	for(int i=1;i<=N;++i){
		cout<<ans[i].fi<<" "<<ans[i].se<<"\n";
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	solve();
	return 0;
}
/*
6
1 3 5 6 4 2
3 5 1 4 6 2

*/