1155 Heap Paths DFS+stack

代码逻辑很简单
构造一颗完全二叉树再DFS
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int n;
struct Node
{
    int value;
    Node *lchild, *rchild;
    Node()
    {
        lchild = rchild = NULL;
    }
};
Node N[1010];
int type = 0;

void show(vector vs)
{
    if (!vs.empty())
    {
        for (int i = 0; i < vs.size(); i++)
        {
            printf("%d", vs[i].value);
            if (i != vs.size() - 1)
            {
                printf(" ");
            }
        }
        printf("n");
    }
}
vector s;
void DFS(int index)
{
    if (index > n)
    {
        if (index % 2 == 0)//左孩子都没了 才输出哦
        {
            show(s);
        }
        return;
    }
    s.push_back(N[index]);
    DFS(index * 2 + 1);
    DFS(index * 2);
    s.pop_back();
}
void isMax()
{
    for (int i = 1; i <= n; i++)
    {
        if (i * 2 < n)
        {
            if (N[i * 2].value > N[i].value || N[i * 2 + 1].value > N[i].value)
            {
                type = -1;
                break;
            }
        }
        if (i == n)
        {
            type = 1;
        }
    }
}
void isMin()
{
    for (int i = 1; i <= n; i++)
    {
        if (i * 2 < n)
        {
            if (N[i * 2].value < N[i].value || N[i * 2 + 1].value < N[i].value)
            {
                type = -1;
                break;
            }
        }
        if (i == n)
        {
            type = 2;
        }
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &N[i].value);
        if (i * 2 <= n)
        {
            N[i].lchild = &N[i * 2];
        }
        if (i * 2 + 1 <= n)
        {
            N[i].rchild = &N[i * 2 + 1];
        }
    }
    isMax();
    if (type == -1)
    {
        isMin();
    }
    if (type == -1)
    {
        type = 0;
    }
    DFS(1);
    if (type == 1)
    {
        printf("Max Heapn");
    }
    else if (type == 2)
    {
        printf("Min Heapn");
    }
    else
    {
        printf("Not Heapn");
    }

    return 0;
}
1155 Heap Paths DFS+stack

C/C++/C#相关栏目本月热门文章
