遍历堆 PAT甲级 1155 堆路径

原题链接

在计算机科学中，堆是一种的基于树的专用数据结构，它具有堆属性：

如果 P 是 C 的父结点，则在大顶堆中 P 结点的权值大于或等于 C 结点的权值，在小顶堆中 P 结点的权值小于或等于 C 结点的权值。

一种堆的常见实现是二叉堆，它是由完全二叉树来实现的。

可以肯定的是，在大顶/小顶堆中，任何从根到叶子的路径都必须按非递增/非递减顺序排列。

你的任务是检查给定完全二叉树中的每个路径，以判断它是否是堆。

输入格式
第一行包含整数 N，表示树中结点数量。

第二行包含 N 个 不同 的整数，表示给定完全二叉树的层序遍历序列。

输出格式
对于给定的树，首先输出所有从根到叶子的路径。

每条路径占一行，数字之间用空格隔开，行首行尾不得有多余空格。

必须以如下顺序输出路径：对于树中的每个结点都必须满足，其右子树中的路径先于其左子树中的路径输出。

最后一行，如果是大顶堆，则输出 Max Heap，如果是小顶堆，则输出 Min Heap，如果不是堆，则输出 Not Heap。

数据范围
1<N≤1000
输入样例1：
8
98 72 86 60 65 12 23 50
输出样例1：
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
输出样例2：
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
输出样例3：
10 15 8
10 15 9
10 28 34
10 28 12 56
Not Heap

我的解法：

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;

int n;
int a[N];
bool lt, gt;

vector <int> path;
void dfs(int u){
    path.push_back(a[u]);
    if(2 * u > n){
        cout << path[0];
        for(int i = 1; i < path.size(); i ++ ) {
            cout << ' ' << path[i];
            if(path[i] < path[i - 1]) gt = true;
            else if(path[i] > path[i - 1]) lt = true;
        }
        cout << endl;
    }
    if(2 * u + 1 <= n) dfs(2 * u + 1);
    if(2 * u <= n) dfs(2 * u);
    path.pop_back();
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> a[i];
    }
    
    dfs(1);
    
    if(lt && gt) puts("Not Heap");
    else if(lt) puts("Min Heap");
    else puts("Max Heap");
    return 0;
}