1167 Cartesian Tree (30 分) PAT

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

这是一道简单题，考察的是数据结构的树和堆，在这个问题，可以有两个解决思路，第一个是建立一个最小堆，每次取出堆顶，就是最小的，然后以这个位置为分界开始递归遍历。

第二个思路是直接在il，ir中寻找到最小的那个下标，并递归遍历。

代码如下：

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 40;

int n, in[N], q[N];
unordered_map l, r, pos;

int dfs(int il, int ir)
{
    priority_queue, greater> heap;
    
    for(int i = il; i <= ir; i ++ ) heap.push(in[i]);
    
    int root = heap.top();
    
    while(heap.size()) heap.pop();
    
    int k = pos[root];
    
    if(k > il) l[root] = dfs(il, k - 1);
    if(k < ir) r[root] = dfs(k + 1, ir);
    
    return root;
}

void bfs(int root)
{
    int hh = 0, tt = 0;
    q[0] = root;
    
    while(hh <= tt)
    {
        int t = q[hh ++];
        
        if (l.count(t)) q[++ tt] = l[t];
        if (r.count(t)) q[++ tt] = r[t];
    }
    
    printf("%d", q[0]);
    
    for(int i = 1; i < n; i ++ ) printf(" %d", q[i]);
    
    printf("n");
}

int main()
{
    scanf("%d", &n);
    
    for(int i = 0; i < n; i ++ ) 
    {
        scanf("%d", &in[i]);
        pos[in[i]] = i;
    }
    
    int root = dfs(0, n - 1);
    
    bfs(root);
    
    return 0;
}

第二种思路的代码如下：

#include 
#include 
#include 
#include 

using namespace std;

const int N = 40;

int seq[N], n, q[N];
unordered_map l, r;

int dfs(int il, int ir)
{
    int k = il;
    for(int i = il + 1; i <= ir; i ++ )
        if(seq[i] < seq[k])
            k = i;
    if(k > il) l[seq[k]] = dfs(il, k - 1);
    if(k < ir) r[seq[k]] = dfs(k + 1, ir);
    
    return seq[k];
}

void bfs(int u)
{
    int hh = 0, tt = 0;
    q[tt] = u;
    
    while(hh <= tt)
    {
        int t = q[hh ++];
        
        if(l.count(t)) q[++ tt] = l[t];
        if(r.count(t)) q[++ tt] = r[t];
    }
    
    printf("%d", q[0]);
    
    for(int i = 1; i < n; i ++ ) printf(" %d", q[i]);
}

int main()
{
    cin >> n;
    
    for(int i = 0; i < n; i ++ ) cin >> seq[i];
    
    int root = dfs(0, n - 1);
    
    bfs(root);
    
    return 0;
}