7-4 Cartesian Tree (30分)

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

题目描述： Cartesian Tree，特意去百度了一下是啥，不懂是啥树，也不影响做题。中文叫笛卡尔树。题目给出这样一棵树的中序遍历，需要你输出他的层序遍历。

看图就能够发现他的构造特点了，就是根结点比左右子结点的值都小。

输入：第一行n表示树中结点的个数，第二行是树的中序遍历结果。

输出：输出该树层序遍历的结果。

解题思路：我写了两种解法，都是通过递归实现，但处理细节有所不同。解法二有些题是会报错的，有点小bug。bug是啥自己分析哈。这里详细解说解法一；首先不需要建树，用vector放中序遍历的值，通过递归可获得树的先序、中序、后序遍历。递归的思想是，每次找到索引l-索引r之间的最小值，该值便是根节点的值啦，然后稍稍修改区间范围即可。再有一个就是用结构体存放每个结点的值及其所在的层序遍历位置，通过sort排序就能简单便捷的得到层序遍历结果了，如果不适用结构体，直接用unorder_map或map或数组存放，会内存超限的！这是测试点2的坑点。

//解法一：
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int n;
vector<int> in;
struct node{
	int index;
	int num;
};
vector<node> level;
bool cmp(node a, node b){
	return a.index < b.index;
}
void dfs(int l, int r, int index){
	if(l>=r) return ;
	int k = 0, mx = inf;
	for(int i=l; i<r; i++){
		if(in[i]<mx){
			mx = in[i];
			k = i;
		}
	}
	node t;
	t.index = index;
	t.num = in[k];
	level.push_back(t);
	dfs(l,k,index*2);
	dfs(k+1,r,index*2+1);
}

int main()
{
	node t;
	scanf("%d", &n);
	in.resize(n);
	for(int i=0; i<n; i++) scanf("%d", &in[i]);
	dfs(0,n,1);
	sort(level.begin(),level.end(),cmp);
	for(int i=0; i<level.size(); i++){
		t = level[i];
		if(i) printf(" ");
		printf("%d", t.num);
	}
	return 0;
}

//解法二：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
vector<int> in, v;
struct node{
	int index;
	int num;
};
vector<node> level;
unordered_map<int,int> p;
bool cmp(node a, node b){
	return a.index < b.index;
}
void dfs(int l, int r, int index){
	node t;
	if(l>=r) return ;
	v = in;
	sort(v.begin()+l,v.begin()+r);
	int k = p[v[l]];
	t.index = index;
	t.num = v[l];
	level.push_back(t);
	dfs(l,k,index*2);
	dfs(k+1,r,index*2+1);
}
int main()
{
	node t;
	scanf("%d", &n);
	in.resize(n);
	for(int i=0; i<n; i++){
		scanf("%d", &in[i]);
		p[in[i]] = i;
	}
	dfs(0,n,1);
	sort(level.begin(),level.end(),cmp);
	for(int i=0; i<level.size(); i++){
		t = level[i];
		if(i) printf(" ");
		printf("%d", t.num);
	}
	return 0;
}