PAT 1110

题目 ： Complete Binary Tree

分值 ： 25
难度 ： 中等题
思路 ： 是否是完全二叉树 判断依据 ：
       层序遍历 第一次出现左右子树不全的节点 应该预示着之后的节点都没有子树 如果之后的子树 还有子节点
       则直接 false
坑点 ： 如果很快想到这个 判断依据是很简单的

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <math.h>
using namespace std;
typedef struct Node
{
    int self ;
    int l =-1;
    int r =-1;
    int rudu=0 ;
}Nodes ;
Nodes data[21] ;
int main() {
    bool flag = true ;
    int N ;
    cin >> N ;
    string s1,s2;
    for(int i = 0 ; i< N ; i++)
    {
        cin>> s1 >>s2;
        data[i].self = i ;
        if(s1=="-" && s2!="-")
        {
            //cout <<"heihei"<<endl ;
            flag = false ;
        }
        if(s1!="-")
        {
            data[i].l = atoi(s1.c_str()) ;
            data[atoi(s1.c_str())].rudu ++;
        }
        if(s2!="-")
        {
            data[i].r = atoi(s2.c_str()) ;
            data[atoi(s2.c_str())].rudu ++;
        }
    }
    int head ;
    for(int i = 0 ; i< N ; i++)
    {
        if(data[i].rudu==0)
        {
            head = i ;
            break ;
        }
    }
    Nodes Queen[21];
    int count = 0 ,cur = 0 ;
    Queen[count++] = data[head] ;
    int end = 0 ;
    while(cur<count)
    {
        if(end&& Queen[cur].l!=-1)
            flag = false ;
        if(Queen[cur].l ==-1 && Queen[cur].r==-1)
            end = 1 ;
        if(Queen[cur].l != -1 )
            Queen[count++] = data[ Queen[cur].l ];
        if(Queen[cur].r != -1 )
            Queen[count++] = data[ Queen[cur].r ] ;
        cur++ ;
    }

    if(flag)
        cout <<"YES "<< Queen[count-1].self <<endl;
    else         cout << "NO " <<head <<endl ;

}