题目描述

判断是大根堆还是小根堆，还是不是堆
Dfs 当访问到叶节点（root*2>n）,输出路径path  输出路径的时候判断是否满足大根堆或者小根堆的性质

算法1

C++ 代码

#include<iostream>
#include<vector>
using namespace std;
const int N=1010;
int a[N*9];
int n;
vector<int> path;
bool is_max=true,is_min=true; //标记是否是大根堆还是小根堆

void dfs(int root){
    if(!root){
        return ;
    }

    //递归到叶子节点输出路径，通过stack存储路径
    path.push_back(a[root]);

    if(root*2>n){
        //输出路径
        cout<<path[0];
        for(int i=1;i<path.size();i++){
            cout<<" "<<path[i];
            //对输出路径进行比较
            if(path[i]<path[i-1]){
                //说明不可能是小根堆
                is_min=false;
            }
            if(path[i]>path[i-1]){
                //说明不可能是大根堆
                is_max=false;
            }
        }
        cout<<endl;
    }

    if(2*root+1<=n){dfs(2*root+1);}
    if(2*root<=n) {dfs(2*root);}

    //将输出的路径弹出，回溯
    path.pop_back();

}

int main(){
    cin>>n;

    for(int i=1;i<=n;i++){
        cin>>a[i];
    }

    dfs(1);

    if(!is_max&&!is_min){
        cout<<"Not Heap"<<endl;
    }
    else if(is_min){
        cout<<"Min Heap"<<endl;
    }else{
        cout<<"Max Heap"<<endl;
    }

    return 0;
}