PAT_1110

1110 Complete Binary Tree

题目描述

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:

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

Sample Output 1:

1
YES 8

Sample Input 2:

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

Sample Output 2:

1
NO 1

思路

本题给出每个节点的子节点,要求判断此树是否为完全二叉树

思路一

第一种思路是使用BFS,最直接的思路判断是否为完全二叉树,依次向下遍历节点,总共分为四种类型的节点:

既包含左子节点又包含右子节点、只包含左子节点、只包含右子节点、以及不包含子节点

imgimgimgimg点击并拖拽以移动

其中只要出现只包含右子节点的情况,就表明一定不是完全二叉树,当出现只包含左子节点或者不包含子节点的情况,就表明后面(按照层次遍历的顺序)的节点都是叶子节点,即能为不包含子节点的情况

思路二

第二种思路为,按照层次遍历的顺序(如果不存在节点,也要进行遍历),当出现不是节点的时候,判断遍历节点的个数,如果等于给定的n,那么表明为此树为完全二叉树,如果不等于n,则表明不是完全二叉树

程序

思路一

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
68
69
70
71
72
73
74
75
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <cmath>
#define INF 0x3f3f3f3f

using namespace std;

const int maxn = 20+5;
int _left[maxn],_right[maxn],root,n;
bool use[maxn];

pair<bool,int> Judge(int root)
{
pair<bool,int> ans;
bool leaf = false;
queue<int> q;
q.push(root);
int p;bool left = false;
while(!q.empty())
{
p = q.front();
q.pop();
if((left && (_left[p] != -1 || _right[p] != -1)) || (_left[p] == -1 && _right[p] != -1))
{
ans.first = false;
ans.second = 0;
return ans;
}


if(_left[p] != -1)
q.push(_left[p]);
if(_right[p] != -1)
q.push(_right[p]);
if((_left[p] != -1 && _right[p] == -1) || (_left[p] == -1 && _right[p] == -1))
left = true; //表示该节点之后的节点都必须为叶子节点
}
ans.first = true;
ans.second = p;
return ans;
}
int main()
{
memset(_left,-1,sizeof(_left));
memset(_right,-1,sizeof(_right));
string x,y;
scanf("%d",&n);
for(int i = 0;i < n;i ++)
{
cin >>x >> y;
if(x != "-")
_left[i] = stoi(x),use[stoi(x)] = 1;

if(y != "-")
_right[i] = stoi(y),use[stoi(y)] = 1;
}
for(int i =0 ;i < n;i ++)
if(!use[i])
{
root = i;break;
}

pair<bool,int> p = Judge(root);
if(p.first == true)
printf("YES %d\n",p.second);
else
printf("NO %d\n",root);
return 0;
}

思路二

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
68
69
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <cmath>
#define INF 0x3f3f3f3f

using namespace std;

const int maxn = 25;
int _left[maxn],_right[maxn],root,n;
bool use[maxn];

void Judge(int root)
{
queue<int> q;
q.push(root);
int p,num = 0,last;
while(!q.empty())
{
p = q.front();
q.pop();

if(p == -1)
{
if(num == n)
printf("YES %d\n",last);
else
printf("NO %d\n",root);
return ;
}
else
last = p,num ++;
q.push(_left[p]);
q.push(_right[p]);

}
return ;

}
int main()
{
memset(use,false,sizeof(use));
memset(_left,-1,sizeof(_left));
memset(_right,-1,sizeof(_right));
string x,y;
cin >> n;
for(int i = 0;i < n;i ++)
{
cin >>x>>y;
if(x != "-")
_left[i] = stoi(x),use[stoi(x)] = 1;

if(y != "-")
_right[i] = stoi(y),use[stoi(y)] = 1;
}
for(int i = 0 ;i < n;i ++)
if(!use[i])
{
root = i;break;
}

Judge(root);
return 0;
}

参考博客

判断一个二叉树是否为完全二叉树

-------------本文结束感谢您的阅读-------------
显示 Gitment 评论