PAT 2019年冬季 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

实现思路：

本题看似题目有提到堆，其实和堆没什么关系，就是一个给中序要求建树的题目，这里的建树递归方法有点类似归并排序的划分，核心是如何确定左子树和右子树，因为要求是堆的结构，又是最小堆，所以可以知道父节点是最小的值，所以只需要每次在子序列中找到最小值，然后作为中间索引，分别划分左子树和右子树进行递归建树即可，然后层序遍历输出。

AC代码：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int inf=(1<<30)-1;
const int N=50;
struct node {
	int x;
	node *l,*r;
};
int sq[N],n,val;

node* dfs(int L,int R) {
	if(L>R) return NULL;
	node *root=new node;
	int MIN=inf,idx;//idx为最小值在数组中的下标索引
	for(int k=L; k<=R; k++) {
		if(sq[k]<MIN) {
			MIN=sq[k];
			idx=k;//找到最小值的index
		}
	}
	root->x=MIN;//填写结点值为最小值
	root->l=dfs(L,idx-1);//根据最小值的下标进行划分左子树和右子树
	root->r=dfs(idx+1,R);
	return root;
}

int cnt=0;
void level(node *root) {
	queue<node*> q;
	q.push(root);
	while(!q.empty()) {
		node *now=q.front();
		printf("%d",now->x);
		cnt++;
		if(cnt<n) printf(" ");
		q.pop();
		if(now->l) q.push(now->l);
		if(now->r) q.push(now->r);
	}
}

int main() {
	cin>>n;
	for(int i=0; i<n; i++) {
		scanf("%d",&sq[i]);
	}
	node *root=dfs(0,n-1);
	level(root);//输出层序遍历
	return 0;
}

PAT 2019年冬季 7-4 Cartesian Tree (30 分)

原文：https://www.cnblogs.com/coderJ-one/p/14423456.html