PAT 1155 Heap Paths （30 分）c++

題目:

題目大意: 給一個二叉樹判斷是否是最大或最小堆. 這道題考察的知識點是遞歸和dfs, 通過一次深度優先的周遊就可以把所有路徑找出來, 每找出一個路徑就判斷一下是不是遞減, 是不是遞增.

注意遞歸題目中, 重點關注邊界條件–到達葉節點, 遞歸式–最小堆的數組存儲, 從1開始, 第i個元素的左兒子是i2, 右兒子是2i + 1.

#include<cstdio>
#include<iostream>
#include<vector>
#define pb push_back 
using namespace std;
int tree[1005];
int n;
bool max_flag = true, min_flag = true;
vector<int> temp_path;

void dfs(int i) {
    temp_path.pb(tree[i]);
    if ( i * 2 > n) {
        for(int i = 0; i < temp_path.size(); i++) {
            printf("%d", temp_path[i]);
            if (i > 0) {
                if (max_flag)
                    max_flag = temp_path[i-1] >= temp_path[i];
                if (min_flag)
                    min_flag = temp_path[i-1] <= temp_path[i];
            }
            if (i + 1 != temp_path.size()) printf(" ");
            else printf("\n");
        }
    }
    else {
        if (i * 2 + 1 <= n) dfs(i * 2 + 1);
        if (i * 2 <= n) dfs(i * 2);
    }
    temp_path.pop_back();
}

int main() {
    scanf("%d", &n);	
    for (int i = 1; i <= n; i++) {
        scanf("%d", &tree[i]);
    }
    dfs(1);
    if (max_flag) printf("Max Heap");
    else if (min_flag) printf("Min Heap");
    else printf("No Heap"); 
    system("pause;");
    return 0;
}