A1167 Cartesian Tree (30 分)

A1167 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

题目大意：

给出一个 min-heap Cartesian tree 的中序遍历序列，输出这颗二叉树的层序遍历。

思路

min-heap Cartesian tree的每个子树都是最小堆，即子树中值最小的结点就是根结点，然后递归遍历就可以恢复二叉树，然后输出层序遍历（可以在恢复二叉树的过程中记录层序遍历的位置，最后直接输出层序遍历就可）

AC代码

1

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> inorder;
map<int, vector<int> > level;

// 这里的deep，可以换为结点的索引根结点为i(编号从1开始)，左孩子结点索引为2*i，右孩子结点索引为2*i+1；
void traversal(int inL, int inR, int deep) {
    if (inL > inR) return;
    int index = inL;
    int MIN = INT_MAX;
    for (int i = inL; i <= inR; ++i) {
        if (inorder[i] < MIN) {
            MIN = inorder[i];
            index = i;
        }
    }
    level[deep].emplace_back(inorder[index]);
    traversal(inL, index - 1, deep + 1); // left;
    traversal(index + 1, inR, deep + 1); // right;
}

int main() {
    scanf("%d", &n);
    inorder = vector<int>(n);
    for (int i = 0; i < n; ++i) {
        cin >> inorder[i];
    }
    traversal(0, n - 1, 0);
    bool isblank = false;
    for (auto &p : level) {
        for (int &t : p.second) {
            if (isblank) printf(" ");
            if (!isblank) isblank = true;
            printf("%d", t);
        }
    }
    return 0;
}

2

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> inorder;
map<int, int> level;

void traversal(int inL, int inR, int x) {
    if (inL > inR) return;
    int index = inL;
    int MIN = INT_MAX;
    for (int i = inL; i <= inR; ++i) {
        if (inorder[i] < MIN) {
            MIN = inorder[i];
            index = i;
        }
    }
    level[x] = inorder[index];
    traversal(inL, index - 1, x * 2); // left;
    traversal(index + 1, inR, x * 2 + 1); // right;
}

int main() {
    scanf("%d", &n);
    inorder = vector<int>(n);
    for (int i = 0; i < n; ++i) {
        cin >> inorder[i];
    }
    traversal(0, n - 1, 1);
    bool isblank = false;
    for (auto &p : level) {
        if (isblank) printf(" ");
        if (!isblank) isblank = true;
        cout << p.second;
    }
    return 0;
}