题目描述
blablabla
样例
#include<iostream>
#include<vector>
using namespace std;
const int N=1010;
int h[N];
int n;
bool gt=false,lt=false;
vector<int>path;
void dfs(int u)
{
path.push_back(h[u]);
if(u>n/2)
{
cout<<path[0];
for(int i=1;i<path.size();i++)
{ cout<<' '<<path[i];
if(path[i-1]<path[i]) gt=true;//not if(path[i+1]<path[i]) gt=true;
else lt=true;
}//bool 值可以一起判断
cout<<endl;//递归是自动for循环 所以每组结束要加endl
}//cout<<h[u]<<' ';u为叶子结点倒着输出
if(2*u+1<=n) dfs(2*u+1);
if(2*u<=n) dfs(2*u);//not 先if(2*u<=n) dfs(2*u); if(2*u+1<=n) dfs(2*u+1);
/*not else
{
if(2*u<=n) dfs(2*u);
if(2*u+1<=n) dfs(2*u+1);
}
*/
path.pop_back();//not path.pop_back(u);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>h[i];
dfs(1);//从根节点开始遍历
if(gt&<) puts("Not Heap");
else if(lt) puts("Max Heap");
else if(gt) puts("Min Heap");
}
#include<iostream>
#include<vector>
using namespace std;
const int N=1010;
int n;
int h[N];
bool gt,lt;
vector<int> path;
void dfs(int u)
{
path.push_back(h[u]);//不管是不是叶节点都进来
if(u*2>n) //说明u是叶节点==u没有左儿子
{
cout<<path[0];
for(int i=1;i<path.size();i++)
{
cout<<' '<<path[i];
if(path[i]>path[i-1]) gt=true;
else lt=true;
}
cout<<endl;
}
if(u*2+1<=n) dfs(u*2+1);
if(u*2<=n) dfs(u*2);
path.pop_back();//操作过了就出去,换一条数列,类似堆栈vector先进后出
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>h[i];
dfs(1);//从根节点开始遍历
if(gt&<) puts("Not Heap");
else if(gt) puts("Min Heap");
else if(lt) puts("Max Heap");
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla