A 1110 Complete Binary Tree

题目链接

Problem Description

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

Input

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

For each case, print in one line YESand the index of the last node if the tree is a complete binary tree, or NOand 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

题目大意：

给出n个节点编号0——n-1，还有n个节点的左右孩子节点，问你构成的这颗二叉树是不是完全二叉树。

解题思路：

将这颗完全二叉树填到一个静态数组中，在根节点为i的情况下，左孩子下标是2i+1、右孩子下标是2i+2 。如果不满足最大的下标是n-1，则不是完全二叉树。

AC代码

#include<bits/stdc++.h>
using namespace std;
struct node{
    int l,r;
}tree[25];
int magic[105],root,n,maxind=0;
string lchild,rchild;
bool flag=true;
vector<int> B[25];

void dfs(int x,int ind){
    maxind=max(maxind,ind);
    magic[ind]=x;
    if(tree[x].l!=-1){
        dfs(tree[x].l,2*ind+1);
    }
    if(tree[x].r!=-1){
        dfs(tree[x].r,2*ind+2);
    }
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        cin>>lchild>>rchild;
        if(lchild!="-"){
            tree[i].l=stoi(lchild);
            B[stoi(lchild)].emplace_back(i);
        }else{
            tree[i].l=-1;
        }
        if(rchild!="-"){
            tree[i].r=stoi(rchild);
            B[stoi(rchild)].emplace_back(i);
        }else{
            tree[i].r=-1;
        }
    }
    for(int i=0;i<n;i++){
        if(B[i].size()==0){
            root=i;
            break;
        }
    }
    dfs(root,0);
    if(maxind==n-1){
        printf("YES %d",magic[n-1]);
    }else{
        printf("NO %d",root);
    }
    return 0;
}