关于算法-数据结构:PAT甲级1155-Heap-Paths

题目粗心：

给定一颗 N 个节点的齐全二叉树的档次序列，须要输入该树的所有从根节点到叶子节点的门路 (优先拜访右子树), 而后判断是否是堆，如果不是输入 Not Heap，否则输入 Max Heap 或者 Min Heap。

算法思路：

应用 heap 数组存储齐全二叉树的档次遍历，无需做任何建树的操作，因为节点的下标之间天然存在父子关系，所以间接应用先序遍历遍历这课树，并且在拜访每一个节点的时候应用 path 数组进行保留，在遇到叶子节点的时候就进行输入，节点拜访结束就回溯，该过程应用 $preTraverse$ 函数来实现。紧接着就是应用 $isMaxHeap$ 和 $isMinHeap$ 变量标记以后齐全二叉树是否是大根堆或者小根堆，初始为 true, 而后应用援用传值到 $isMaxOrMinHeap$ 中，同时判断是否是大根堆或者小根堆，这里采纳负向逻辑，只有有左孩子，左孩子小于根节点的阐明不是小根堆，否则阐明不是大根堆，右孩子亦然如此。最初依据 $isMaxHeap$ 和 $isMinHeap$ 的值进行相应的输入即可。

提交后果：

AC 代码：

#include<cstdio>
#include<vector>

using namespace std;

int N;
int heap[1005];
vector<int> path;

void preTraverse(int root){if(rreoot>N) return;
    // 先拜访以后节点，因为这样就能够在遇到叶子节点的时候失去一个从根节点到叶子节点的门路
    path.push_back(heap[root]);
    if(2*root>N&&2*root+1>N){
        // 达到叶子节点, 输入该门路即可
        for(int i=0;i<path.size();++i){printf("%d",path[i]);
            if(i<path.size()-1) printf(" ");
        }
        printf("\n");
    }
    preTraverse(2*root+1);
    preTraverse(2*root);
    path.pop_back();}

void isMaxOrMinHeap(bool &isMaxHeap,bool &isMinHeap){for (int i = 1; i <= N; ++i) {if((2*i<=N&&heap[i]<heap[2*i])||(2*i+1<=N&&heap[i]<heap[2*i+1])){isMaxHeap = false;}
        if((2*i<=N&&heap[i]>heap[2*i])||(2*i+1<=N&&heap[i]>heap[2*i+1])){isMinHeap = false;}
    }
}

int main(){scanf("%d",&N);
    for (int i = 1; i <= N; ++i) {scanf("%d",&heap[i]);
    }
    postTraverse(1);
    bool isMaxHeap = true;
    bool isMinHeap = true;
    isMaxOrMinHeap(isMaxHeap,isMinHeap);
    if(isMaxHeap){printf("Max Heap");
    } else if(isMinHeap){printf("Min Heap");
    } else {printf("Not Heap");
    }
    return 0;
}