1086 Tree Traversals Again (25 分)

题目

题目链接

题解

数据结构。

这道题的核心在于非递归形式的中序遍历，每次push操作的顺序是树的前序遍历，而pop操作的顺序是树的中序遍历。详细点说，每次push进去的元素按顺序排列就是前序遍历，pop弹出的元素按顺序排列就是中序遍历。

问题转化为了已知前序遍历和中序遍历，求后序遍历。

扩展思考：

已知非递归形式的中序遍历求树的前序遍历和中序遍历会了，那么如果已知前序遍历和中序遍历，要如何求非递归形式的中序遍历呢？

双指针，顺序遍历前序遍历序列，遍历到就无条件入栈，入栈后判断另一指针指向的中序遍历序列是否与栈顶元素相等，相等就不停地出栈，同时指针后移。

不知道健壮性如何。

代码

#include
using namespace std;
const int N = 1e5+10;
// 1 2 3 4 5
int idx = 1;
int n;
int a[N];
vector  v, inorder, preorder;
stack  stk;

void postorder (int l1, int r1, int l2, int r2) {
	// 这个函数太容易写错了，很多小细节 
	if (l2 > r2) return ;
	int rt = preorder[l1], p = l2; // p初始化为l2 
	while (p > n;
	int T = (n  op;
		if (op.back () == 'h') { // push
			int x;
			cin >> x;
			stk.push (x);
			preorder.push_back (x);
		} else {
			inorder.push_back (stk.top ());
			stk.pop ();
		}
	}	
	
	postorder (0, n-1, 0, n-1);
	
	for (int i = 0, flag = 0;i