PAT-A-1086-Tree Traversals Again

An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.

Figure 1

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: “Push X” where X is the index of the node being pushed onto the stack; or “Pop” meaning to pop one node from the stack.

Output Specification:

For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

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

Sample Output:

3 4 2 6 5 1

Code

#include <iostream>
#include <string>
#include <stack>
using namespace std;
int preSeq[30], inOrder[30], preIdx = 0, inIdx = 0;

struct node {
	int data;
	node* lc, * rc;
	node(int _data) :data(_data), lc(0), rc(0) {}
};

node* buildTree(int preL, int preR, int inL, int inR) {
	if (preL > preR)
		return 0;
	node* root = new node(preSeq[preL]);
	int i;
	for (i = inL;i <= inR;i++) {
		if (preSeq[preL] == inOrder[i])
			break;
	}
	int lnum = i - inL;//不包括自己，左子树的节点总和
	root->lc = buildTree(preL + 1, preL + lnum, inL, i - 1);
	root->rc = buildTree(preL + 1+ lnum, preR, i + 1, inR);
	return root;
}

int current = 0;
void postOrder(node* root) {
	if (root != 0) {
		postOrder(root->lc);
		postOrder(root->rc);
		if (current++ == 0)
			printf("%d", root->data);
		else
			printf(" %d", root->data);
	}
}


int main() {
	int n;
	scanf("%d", &n);
	//每次访问一个节点就入栈，相当于先序遍历
	//而pop是按照左右根的顺序，相当于中序遍历
	stack<int> stk;
	string temp;
	int num;
	//先获得先序和中序序列
	for (int i = 0;i < 2 * n;i++) {
		cin >> temp;
		if (temp == "Push") {
			cin >> num;
			stk.push(num);
			preSeq[preIdx++] = num;
		}
		else {
			inOrder[inIdx++] = stk.top();
			stk.pop();
		}
	}

	node* root = buildTree(0, preIdx - 1, 0, inIdx - 1);
	postOrder(root);
	
	return 0;
}