PAT甲级1155 Heap Paths (30 分)：[C++题解]堆、堆的遍历、树的遍历、dfs输出路径、完全二叉树建树

本文主要是介绍PAT甲级1155 Heap Paths (30 分)：[C++题解]堆、堆的遍历、树的遍历、dfs输出路径、完全二叉树建树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 题目分析
- 题目链接

题目分析

在这里插入图片描述

来源：acwing

分析:

堆首先是完全二叉树，所以先建完全二叉树，由于给定的是层序遍历的数据，所以直接用数组即可，注意数组下标从1开始，这样便满足结点u和左儿子、右儿子的关系：下标分别是是u*2和u*2+1。
然后就是树的dfs遍历，需要输出每条路径，并且需要判断单调关系，另外是先输出右儿子的路径，再输出左儿子的路径。对应到dfs的实现，就是先dfs(u*2+1),再dfs(2 *u);

ac代码

#include<bits/stdc++.h>
using namespace std;
const int N  =1010;int n;
int h[N];
bool gt, lt;
vector<int> path; //dfs求路径
//相当于前序遍历
void dfs(int u){//u结点先加入路径path.push_back(h[u]);//叶子结点if(u*2 > 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(u*2+1 <=n ) dfs(u*2 +1);//再输出左儿子if(u*2 <= n) dfs(u*2);//恢复现场，把插入的u结点删除path.pop_back();
}int main(){cin >> n;//从编号1开始，1是根结点for(int i =1; i<=n; i++) cin >> h[i];//从根节点开始dfsdfs(1);if(gt && lt) cout<<"Not Heap"<<endl;else if(gt) cout<<"Min Heap"<<endl;else cout<<"Max Heap"<<endl;}