PAT甲级1155题（堆路径）

数据结构题

PAT

发布日期: 2021-02-08

文章字数: 216

阅读时长: 1 分

阅读次数:

1.题目介绍

1155

2.考察点，难度

堆数据结构，Vector容器使用方法，递归，难度中

3.解题代码

#include <iostream>
#include <vector>
using namespace std;
vector<int> v;
int a[1009], n, isMin = 1, isMax = 1;

void dfs(int index) {
    if (index * 2 > n && index * 2 + 1 > n) {   // 处于叶子节点处
        if (index <= n) {
            for (int i = 0; i < v.size(); i++)
                printf("%d%s", v[i], i != v.size() - 1 ? " " : "\n");
        }
    } else {        // 递归更新v
        v.push_back(a[index * 2 + 1]);
        dfs(index * 2 + 1);
        v.pop_back();
        v.push_back(a[index * 2]);
        dfs(index * 2);
        v.pop_back();
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    v.push_back(a[1]);
    dfs(1);
    for (int i = 2; i <= n; i++) {  // 判断顺序
        if (a[i/2] > a[i]) isMin = 0;
        if (a[i/2] < a[i]) isMax = 0;
    }
    if (isMin == 1)
        printf("Min Heap");
    else
        printf("%s", isMax == 1 ? "Max Heap" : "Not Heap");
    return 0;
}