1086 Tree Traversals Again (25 分)

题目传送门：1086 Tree Traversals Again (25 分)

一、题目大意

这道题的难点就在于是否能读懂题意了。。。题目说的神乎其神，看似在用栈模拟二叉树的构造，以一种压栈顺序，出栈的顺序就是中序。仔细研究下发现入栈顺序是二叉树的先序（题目好像没说明是先序入栈，只说按1-n入栈），而出栈顺序是中序。那么既然有了先中序，想获得后序就so easy了

二、解题思路

常规套路，二叉树先中序转后序，直接看代码吧

三、AC代码

#include<bits/stdc++.h>
using namespace std;
vector<int>preorder, inorder, postorder;
map<int, int>M;
void dfs(int preLeft, int preRight, int inLeft, int inRight){
	if(preLeft > preRight)return;
	int val = preorder[preLeft];
	int p = inLeft;
	for(int i = inLeft; i <= inRight; i++){
		if(inorder[i] == val){
			p = i;
			break;
		}
	}
	int len = p - inLeft;
	dfs(preLeft+1, preLeft+len, inLeft, p-1);
	dfs(preLeft+len+1, preRight, p+1, inRight);
	postorder.push_back(val);
}
int main(){
	int n;
	cin >> n;
	stack<int>Stk;
	for(int i = 0; i < 2*n; i++){
		string s;
		cin >> s;
		if(s == "Push"){
			int x;
			cin >> x;
			preorder.push_back(x);
			Stk.push(x);
		}else{
			inorder.push_back(Stk.top());
			Stk.pop();
		}
	}
	assert(preorder.size() == inorder.size());
	dfs(0, preorder.size()-1, 0, inorder.size()-1);
	for(int i = 0; i < postorder.size(); i++){
		if(i)cout << " " << postorder[i];
		else cout << postorder[i];
	}
	cout << endl;
}

  

 

  
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
 

文章来源: blog.csdn.net，作者：爱玲姐姐，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/jal517486222/article/details/100184739