PAT甲级1155.

目录

A1155

题目

样例

样例1

输入:

8
98 72 86 60 65 12 23 50

输出:

98 86 23
98 86 12
98 72 65
98 72 60 50
Max Heap

样例2

输入:

8
8 38 25 58 52 82 70 60

输出:

8 25 70
8 25 82
8 38 52
8 38 58 60
Min Heap

样例3

输入:

8
10 28 15 12 34 9 8 56

输出:

10 15 8
10 15 9
10 28 34
10 28 12 56
Not Heap

思路和坑点

　　思路：
　　使用库函数判断是不是堆，然后dfs获取路径，这里注意题目要求先右节点再左节点路径。

AC代码

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> v;                                      //存放堆的各个顶点
vector<int> path;                                   //存放路径
void getpath(int i);
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    scanf("%d",&n);
    v.resize(n);
    for(int i=0;i<n;i++)                            //读入堆的结点
        scanf("%d",&v[i]);
    getpath(0);
    if(is_heap(v.begin(),v.end(),less<int>()))      //使用stl中的函数判断堆
        puts("Max Heap");
    else if(is_heap(v.begin(),v.end(),greater<int>()))
        puts("Min Heap");
    else 
        puts("Not Heap");
    return 0;    
}
void getpath(int i){                                //获取根到结点的路径
    if(i*2+1>=n&&i<n){                              //如果已经到了最后一层
        path.push_back(v[i]);                       //加入最后一个叶子结点
        for(int j=0;j<path.size();j++){             //输出路径
            if(j) putchar(' ');
            printf("%d",path[j]);
        }
        putchar('\n');
        path.pop_back();                            //回退一个元素返回到上一层
        return;
    }
    else if(i>=n)    return;                        //如果当前结点为空直接返回上一层
    path.push_back(v[i]);                           //放入当前结点
    getpath(i*2+2);                                 //获取右子树叶子结点路径
    getpath(i*2+1);                                 //获取左子树叶子结点路径
    path.pop_back();                                //回退一个元素返回到上一层
}