19年冬季第四题 PAT甲级 1167 Cartesian Tree (30分)超级详解不AC都难

痛定思痛。 2023-07-02 07:23 7阅读 0赞

## 题目： ##

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.

![CTree.jpg][]

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

## 题目大意： ##

给定一个二叉最小堆（Cartesian Tree）的中序序列，输出层序遍历序列。

## 这道题的题眼： ##

1.给出的是个min-heap  
最小堆，即所有父节点不大于子节点的二叉树。如果找到了目前区间的最小值，那就是个父节点。  
2.给出的顺序是inorder  
中序，也就是LNR。是不是想到了递归和分而治之的老方法了？  
3.输出的顺序是level-order  
层序。如果不建树，就是开个大数组，按照下标放；如果建树，就得用BFS遍历树了。

## 这道题的陷阱： ##

没有说是哪种二叉树，如果是最极端的那种，就是每行只有一个节点，画个草图就是：  
![在这里插入图片描述][20200127190755894.png]  
4是3的左孩子，3是2的左孩子，2是1的左孩子。  
题目说最多30个节点，如果不建树那得需要2的30次方那么大的数组了，那会遇到编译不通过。所以这道题还得建树。

## 我自己写的测试用例： ##

改变节点的数量和二叉树的内部结构。不过这道题本身是没啥坑的。

//输入1
    8
    60 58 38 52 8 82 25 70
    //输出1
    8 38 25 58 52 82 70 60
    
    //输入2
    13
    8 4 2 9 5 10 1 11 6 12 3 7 13
    //输出2
    1 2 3 4 5 6 7 8 9 10 11 12 13

## 附上满分答案： ##

#include<iostream>
    #include<queue>
    using namespace std;
    int n,k;
    vector<int> v;
    struct tree{ 
        int data;
        tree *l,*r;
    }*T;
    tree* check(int low,int high){ 
        if(low<0||low>high)return NULL;
        tree *t=new tree;
        int minn=low;
        for(int j=low;j<=high;j++){ 
            if(v[minn]>v[j])minn=j;
        }
        t->data=v[minn];
        t->l=check(low,minn-1);
        t->r=check(minn+1,high);
        return t;
    }
    int main(){ 
        scanf("%d",&n);
        for(int i=0;i<n;i++){ 
            scanf("%d",&k);
            v.push_back(k);
        }
        T=check(0,n-1);
        int flag=0;
        queue<tree*> q;
        q.push(T);
        while(!q.empty()){ 
            tree *t=q.front();
            if(flag==1)cout<<" ";
            else flag=1;
            cout<<t->data;
            if(t->l)q.push(t->l);
            if(t->r)q.push(t->r);
            q.pop();
        }
        return 0;
    }

[CTree.jpg]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMucHRhdXNlcmNvbnRlbnQuY29tLzZhOTlmNjhhLTY1NzgtNDZlMC05MjMyLWZiZjBhZGYzNjkxZi5qcGc?x-oss-process=image/format,png
[20200127190755894.png]: https://img-blog.csdnimg.cn/20200127190755894.png