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

思路&分析

给出了一组树的

inorder traversal

中序遍历结果，用最小堆的形式建树。因为中序遍历根节点在中间，最小堆的根节点最小，那么每次从序列中找到最小值就是根，左半部分为左子树，右半部分为右子树，递归建树即可。最后根据题目要求用队列输出层次遍历结果。

注意点：

感觉没什么注意点…虽然是最后一题，但确是通过率最高的一题（通过率与分值成正比 :smile）建树基本功。

提交代码(AC)

#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#define INF 0x3fffffff

using namespace std;
int in[40];


struct node{
    int data;
    node *left,*right;
};

node * create(int lnum,int rnum){
    if(lnum>rnum) return NULL;

    int k=lnum,MIN=INF;
    for(int i=lnum;i<=rnum;i++){
        if(in[i]<MIN){
            k=i;MIN=in[i];
        }
    }
    node *root=new node();
    root->data=in[k];
    root->left=create(lnum,k-1);
    root->right=create(k+1,rnum);
    return root;
}

int main()
{
//    freopen("1.txt","r",stdin);
    int n;
    cin>>n;

    for(int i=1;i<=n;i++){
        cin>>in[i];
    }
    node * root=create(1,n);

    vector<int> res;
    queue<node *> q;
    q.push(root);
    while(!q.empty()){
        node *f=q.front();
        q.pop();
        res.push_back(f->data);
        if(f->left) q.push(f->left);
        if(f->right) q.push(f->right);
    }
    for(int i=0;i<res.size();i++){
        cout<<res[i];
        if(i!=res.size()-1) cout<<" ";
    }

    return 0;
}