【1155】Heap Paths (30分)【DFS回溯&堆】

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>  
#include<map>
#include<vector>
#include<queue> 
using namespace std;  
int n,a[1009];
vector<int> v;//保存一路上的结点
int isMin=1,isMax=1;
/* 题意：
给⼀完全二叉树，打印从根到所有叶的路径，打印顺序先右后左，即先序
遍历的镜像，判断该树是啥种堆
分析：
1.dfs打印出所有路路径（从右往左，即先序的镜像），vector保存一路上的节点，通过push和
pop回溯，维护路径
2.判断是否为堆：从第2个节点开始遍历，若比父节点大则非小顶堆，若比父节点大则非大顶堆*/
//level order traversal是层序遍历~BFS
//堆is一棵完全二叉树
void dfs(int index){
  if(index>n) 
        return;//判断是否为空结点
  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{ //此处也可以没有else，但要在上面的if结尾加return
    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]);//存入BFS序列
  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");
  system("pause");
  return 0;
}