1086.md

1086

• 1086 Tree Traversals Again (25 point(s))

• According to the preorder traversal sequence and inorder traversal sequence to create a binary tree.

#include <iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

int N;
const int MAX_N = 30 + 5;
vector<int> in, pre, res;
stack<int> s;

struct Node {
	int val;
	Node* l;
	Node* r;
};

Node* create(int preL, int preR, int inL, int inR) {
	if (preL > preR) {
		return NULL;
	}
	Node* root = new Node();
	root->val = pre[preL];
	int i = inL;
	for (; i <= inR; i++) {
		if (in[i] == root->val) {
			break;
		}
	}
	int numLeft = i - inL;
	root->l = create(preL + 1, preL + numLeft, inL, i - 1);
	root->r = create(preL + numLeft + 1, preR, i + 1, inR);
	return root;
}

void postOrder(Node* root) {
	if (root == NULL) {
		return;
	}
	postOrder(root->l);
	postOrder(root->r);
	res.push_back(root->val);
}

int main() {
	cin >> N;
	for (int i = 0; i < 2 * N; i++) {
		string str;
		cin >> str;
		if (str == "Pop") {
			in.push_back(s.top());
			s.pop();
		}
		else {
			int num;
			cin >> num;
			s.push(num);
			pre.push_back(num);
		}
	}
	/*
	for (int i = 0; i < pre.size(); i++) {
		cout << pre[i] << " ";
	}
	cout << endl;
	for (int i = 0; i < in.size(); i++) {
		cout << in[i] << " ";
	}
	cout << endl;
	// */
	Node* root = create(0, pre.size() - 1, 0, in.size());
	postOrder(root);
	for (int i = 0; i < res.size(); i++) {
		cout << res[i];
		if (i < res.size() - 1) {
			cout << " ";
		}
	}
	cout << endl;
	return 0;
}

/*
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
*/

References