1576. 再次树遍历

原题传送：AcWing 1576. 再次树遍历

通过使用栈可以以非递归方式实现二叉树的中序遍历。

例如，假设遍历一个如下图所示的 6 6 6 节点的二叉树（节点编号从 1 1 1 到 6 6 6 ）。

则堆栈操作为：push(1);push(2);push(3);pop();pop();push(4);pop();pop();push(5);push(6);pop();pop()。

我们可以从此操作序列中生成唯一的二叉树。

你的任务是给出这棵树的后序遍历。

输入格式

第一行包含整数 N N N ，表示树中节点个数。

树中节点编号从 1 1 1 到 N N N 。

接下来 2 N 2N 2N 行，每行包含一个栈操作，格式为：

• Push X，将编号为 X X X 的节点压入栈中。
• Pop，弹出栈顶元素。

输出格式

输出这个二叉树的后序遍历序列。

数据保证有解，数和数之间用空格隔开，末尾不能有多余空格。

数据范围

1 ≤ N ≤ 30 1 \le N \le 30 1≤N≤30

输入样例：

6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop

输出样例：

3 4 2 6 5 1

思路：

Push为前序遍历，Pop为中序遍历，构造一棵树并保存后序遍历的序列。

题解：

#include<bits/stdc++.h>

using namespace std;

const int N = 40;

int n, k1 = 0, k2 = 0;
stack<int> s;
int inorder[N], preorder[N];
int postorder[N], cnt;

bool build(int il, int ir, int pl, int pr)
{
	if(il > ir)
		return true;
		
	int root = preorder[pl];
	int k;
	for(k = il; k <= ir; k++)
		if(inorder[k] == root)
			break;
	if(k > ir)
		return false;
	
	bool res = true;
	if(!build(il, k - 1, pl + 1, pl + 1 + (k - 1 - il)))
		res = false;
	if(!build(k + 1, ir, pl + 1 + (k - 1 - il) + 1, pr))
		res = false;
		
	postorder[cnt++] = root;
	return res;
}

int main()
{	
	cin >> n;
	for(int i = 0; i < n * 2; i++)
	{
		string t;
		cin >> t;
		if(t == "Push")
		{
			int num;
			cin >> num;
			s.push(num);
			preorder[k1++] = num;
		}
		else
		{
			int top = s.top();
			inorder[k2++] = top;
			s.pop();
		}
	}
	
	build(0, n - 1, 0, n - 1);
	
	cout << postorder[0];
	for(int i = 1; i < n; i++)
		cout << " " << postorder[i];
	cout << endl;
	
	return 0;
}