PAT A1167 Cartesian Tree (30point(s))

Scroll Down

A Cartesian tree is a binary tree constructed from a sequence of distinct numbers. The tree is heap-ordered, and an inorder traversal returns the original sequence. For example, given the sequence { 8, 15, 3, 4, 1, 5, 12, 10, 18, 6 }, the min-heap Cartesian tree is shown by the figure.

Your job is to output the level-order traversal sequence of the min-heap Cartesian tree.

Input Specification:

Each input file contains one test case. Each case starts from giving a positive integer N (≤30), and then N distinct numbers in the next line, separated by a space. All the numbers are in the range of int.

Output Specification:

For each test case, print in a line the level-order traversal sequence of the min-heap Cartesian tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the beginning or the end of the line.

Sample Input:

10
8 15 3 4 1 5 12 10 18 6

Sample Output:

1 3 5 8 4 6 15 10 12 18

解答

#include<iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>
#include<queue>

using namespace std;

typedef struct node {
	int data;
	struct node *lchild, *rchild;
}node;

unordered_map<int, int> mp;

node* build(vector<int> &nodes, int low, int high) {
	if (low > high) return NULL;
	vector<int> tmp = nodes;
	sort(tmp.begin() + low, tmp.begin() + high + 1);
	int data = tmp[low], mid = mp[data];
	node *root = new node();
	root->data = data;
	root->lchild = build(nodes, low, mid - 1);
	root->rchild = build(nodes, mid + 1, high);
	return root;
}

int main() {
	int n;
	scanf("%d", &n);
	vector<int> nodes(n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &nodes[i]);
		mp[nodes[i]] = i;
	}
	node *root = build(nodes, 0, n - 1);
	queue<node*> q;
	q.push(root);
	while (!q.empty()) {
		printf("%d", q.front()->data);
		if (q.front()->lchild) q.push(q.front()->lchild);
		if (q.front()->rchild) q.push(q.front()->rchild);
		q.pop();
		printf("%s", q.empty() ? "" : " ");
	}
	return 0;
}