1110. Complete Binary Tree (25)

喜欢ヅ旅行 2022-05-28 07:51 156阅读 0赞

Given a tree, you are supposed to tell if it is a complete binary tree.

**Input Specification:**

Each input file contains one test case. For each case, the first line gives a positive integer N (<=20) which is the total number of nodes in the tree -- and hence the nodes are numbered from 0 to N-1. Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a "-" will be put at the position. Any pair of children are separated by a space.

**Output Specification:**

For each case, print in one line "YES" and the index of the last node if the tree is a complete binary tree, or "NO" and the index of the root if not. There must be exactly one space separating the word and the number.

**Sample Input 1:**

9
    7 8
    - -
    - -
    - -
    0 1
    2 3
    4 5
    - -
    - -

**Sample Output 1:**

YES 8

**Sample Input 2:**

8
    - -
    4 5
    0 6
    - -
    2 3
    - 7
    - -
    - -

**Sample Output 2:**

NO 1

--------------------

题目大意：

代码：

#include<stdio.h>
    #include<stdlib.h>
    #include<queue>
    using namespace std;
    struct node
    {
       int lchild,rchild;
    }tree[50];
    int a[50];
    int b[50];
    int main()
    {
        int i,j,n,m,k,t,l,r,root;
        char str1[5],str2[5];
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
           scanf("%s %s",str1,str2);
           if(str1[0]!='-')
           {
              l=atoi(str1);
              a[l]=1;
              tree[i].lchild=l;
           }
           else
           {
              tree[i].lchild=-1;
           }
           if(str2[0]!='-')
           {
              r=atoi(str2);
              a[r]=1;
              tree[i].rchild=r;
           }
           else
           {
              tree[i].rchild=-1;
           }
        }
        for(i=0;i<n;i++)
        {
            if(a[i]==0)
                break;
        }
        root=i;
        j=0;
        queue<int> q;
        q.push(root);
        int lastcode=0;
        int num=0;
        while(!q.empty())
        {
            int tmp=q.front();
            q.pop();
            if(tmp!=-1)
            {
                q.push(tree[tmp].lchild);
                q.push(tree[tmp].rchild);
                num++;
                lastcode=tmp;
            }
            else
            {
                if(num==n)
                {
                    printf("YES %d\n",lastcode);
                }
                else
                {
                    printf("NO %d\n",root);
                }
                return 0;
            }
        }
        return 0;
    }