PAT——1155 Heap Paths (30分)——堆、遍历搜索

偏执的太偏执、 2023-06-29 05:59 32阅读 0赞

考的知识：

*  堆的概念
 *  遍历DFS(根右左的 先序遍历)

/**** 思路明确 注意该题 所有结点的值都不相同（所以不用考虑 全部相等的情况） ****/
    
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<iostream>
    #include<algorithm>
    #include<vector>
    #include<set>
    using namespace std;
    
    int hp[10005];
    int n;
    int path[10005];
    int sz = 0;
    bool decreas = false;
    bool increas = false;
    void proOrder(int i)
    { 
        if(i >= n)return;
    
        path[sz++] = hp[i];
        if(i*2+1>= n) // 判断是否为叶子
        { 
            int mx = 0;
            int mi = 0;
            for(int j = 0;j < sz;j++)
            { 
                if(j < sz-1)
                { 
                    cout<<path[j]<<" ";
                    if(path[j] < path[j+1])increas = true;
                    if(path[j]> path[j+1])decreas = true;
                }
                else
                { 
                    cout<<path[j]<<endl;
                }
            }
            
        }
    
        proOrder(i*2+2);
        proOrder(i*2+1);
        sz--;
    }
    int main()
    { 
        ios::sync_with_stdio(false);
    
        cin>>n;
        for(int i = 0;i < n;i++)
            cin>>hp[i];
        proOrder(0);
        if(!increas)// 如果路径没有出现过增加， 则是大顶堆
        { 
            cout<<"Max Heap"<<endl;
        }
        else if(!decreas)// 如果路径没有出现过降低
        { 
            cout<<"Min Heap"<<endl;
        }
        else cout<<"Not Heap"<<endl;
    
    
    
    
        return 0;
    }