1167 Cartesian Tree – 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

题目大意：笛卡尔树，是由一系列不同数字构成的二叉树。树是堆排序的，中序遍历返回原始序列。例如，给定序列{8, 15, 3, 4, 1, 5, 12, 10, 18, 6}，小顶堆笛卡尔树如图所示。你的工作是输出小顶堆笛卡尔树的层序遍历序列。输入格式：给一个正整数N，接下来一行给出N个不同的数字，用空格分隔。所有数字都在int范围内。输出格式：在一行中输出小顶堆笛卡尔树的层序遍历。一行中的所有数字必须用一个空格隔开，并且行首和行尾不得有多余的空格。

分析：中序遍历保存在In数组中，层序遍历结果保存在映射map ans中。本题需要将小顶堆的中序遍历转化为层次遍历。我们知道，在小顶堆中，数值最小的那个元素为根结点，对于其任何子树也一样。所以我们只要在中序遍历中找到最小的那个数作为当前的根结点，左边的所有数都归左子树，右边所有数都归右子树。将根结点的序号设为1，左孩子的序号为它的两倍，右孩子的序号为它的两倍+1，最后根据序号顺序输出ans即为层序遍历的顺序。哇呜。

#include 
#include 
using namespace std;
int n, In[32];
map<int, int> ans;
void deal(int index, int L, int R) {
    if (L > R) return;
    int pos = L;
    for (int i = L + 1; i <= R; i++)
        if (In[i] < In[pos]) pos = i;
    ans[index] = In[pos];
    deal(index << 1, L, pos - 1);
    deal(index << 1 | 1, pos + 1, R);
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> In[i];
    deal(1, 0, n - 1);
    for (auto it : ans) {
        if (it.first != 1) cout << ' ';
        cout << it.second;
    }
    return 0;
}