文章目录
前言
今日完成任务：
1、单词150旧+50新
2、英语阅读手译一篇
3、英语练字
4、Java核心技术（回顾基础篇）（1.30h）
5、springBoot框架回顾（1.30h）
6、阅读毕设参考材料
7、Pat一题（1110）
提示：以下是本篇文章正文内容，下面案例可供参考
1110 Complete Binary Tree (25 分)
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
分析
题目意思很简单就是给出二叉树判断是否是完全二叉数，只是要ac的话没有什么需要思考的，按照完全二叉的性质除了最后一行，其他各行必须满结点，那么久可以利用层次遍历去设计判断函数即可。
//定义结构体，index是当前节点的索引值
struct node{
int left, right, index;
};
bool isComplate(int root, node tree[]){
//层次遍历需要用到辅助队列
queue<node> q;
q.push(tree[root]);
//用flag 标识当前有左孩子或右孩子为空的情况
bool flag = false;
while(!q.empty()){
node t = q.front();
rear = t.index;
q.pop();
if(t.left != -1){
//当前有节点的左孩子或者右孩子为空，那么后续节点不能再有孩子节点入队，若有则直接返回false
if(flag == true){
return false;
}
q.push(tree[t.left]);
}else{
//有节点的左或右孩子为空
flag = true;
}
if(t.right != -1){
if(flag == true){
return false;
}
q.push(tree[t.right]);
}else{
//有节点的左或右孩子为空
flag = true;
}
}
return true;
}
后续就是对输入输出的操作稍微注意一下，由于输入的有数字和字符“-”，所以最好用字符串去接收，再判断排除等于“-”的情况，利用stoi函数将数值字符串转成int类型。
int main(){
int n , root = 0;
cin >> n;
node tree[n];
//判断是否为树根，如果为树根则没有父节点
bool isNotRoot[n];
//注意对
memset(isNotRoot, false , sizeof isNotRoot);
for(int i = 0 ; i < n; i++){
node temp;
string a, b;
cin>> a >> b;
if(a == "-"){
temp.left = -1;
}else{
//将a转成int类型存入temp
temp.left = stoi(a);
//当有父节点，则不是树根
isNotRoot[stoi(a)] = true;
}
if(b == "-"){
temp.right = -1;
}else{
temp.right = stoi(b);
isNotRoot[stoi(b)] = true;
}
temp.index = i;
tree[i] = temp;
}
//找到树根
for(int i = 0 ; i < n ; i++){
if( !isNotRoot[i] ){
root = i;
}
}
int flag = isComplate(root, tree);
if(flag){
cout<< "YES"<<" "<<rear;
}else{
cout<< "NO"<<" "<<root;
}
return 0;
}
顺便简单补充一下stoi()和atoi()。
1、头文件都是#include
2、都是C++的字符处理函数，把数字字符串转换成int输出
3、 atoi()的参数是 const char* ,因此对于一个字符串str我们必须调用 c_str()的方法把这个string转换成 const char类型的
4、stoi()的参数是const string&,不需要转化为 const char；
AC代码
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
struct node{
int left, right, index;
};
int rear;
//层次遍历
bool isComplate(int root, node tree[]){
queue<node> q;
q.push(tree[root]);
bool flag = false;
while(!q.empty()){
node t = q.front();
rear = t.index;
q.pop();
if(t.left != -1){
if(flag == true){
return false;
}
q.push(tree[t.left]);
}else{
flag = true;
}
if(t.right != -1){
if(flag == true){
return false;
}
q.push(tree[t.right]);
}else{
flag = true;
}
}
return true;
}
int main(){
int n , root = 0;
cin >> n;
node tree[n];
bool isNotRoot[n];
memset(isNotRoot, false , sizeof isNotRoot);
for(int i = 0 ; i < n; i++){
node temp;
string a, b;
cin>> a >> b;
if(a == "-"){
temp.left = -1;
}else{
temp.left = stoi(a);
isNotRoot[stoi(a)] = true;
}
if(b == "-"){
temp.right = -1;
}else{
temp.right = stoi(b);
isNotRoot[stoi(b)] = true;
}
temp.index = i;
tree[i] = temp;
}
for(int i = 0 ; i < n ; i++){
if( !isNotRoot[i] ){
root = i;
}
}
int flag = isComplate(root, tree);
if(flag){
cout<< "YES"<<" "<<rear;
}else{
cout<< "NO"<<" "<<root;
}
return 0;
}
简化
这道题只是要做出来是挺简单的，但是我查阅了其他大神的解法才发现自己也太垃圾了，其实根据完全二叉树的定义：
一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
很快就能发现，只用统计二叉树中的最后一个节点再完全二叉树中的下标位置，如果下标位置与节点数相同则是完全二叉树。比如样例2：由于最后一个节点6若在完全二叉树情况下的下标为9，大于节点个数则原树不是完全二叉树。
根据上述分析，则可以利用dfs去递归判断每个节点的下标，快速判断是否为完全二叉树。修改后的代码如下：
int rear, maxn;
//dfs代码参考柳神
void dfs(int root, int index, node tree[]) {
//德昂当前下标大于最大下标时
if(index > maxn) {
maxn = index;
//最后一个节点的索引一定是下标最大的节点索引
rear = root;
}
if(tree[root].left != -1) dfs(tree[root].left, index * 2, tree);
if(tree[root].right != -1) dfs(tree[root].right, index * 2 + 1, tree);
}
int main(){
int n , root = 0;
cin >> n;
node tree[n];
bool isNotRoot[n];
memset(isNotRoot, false , sizeof isNotRoot);
for(int i = 0 ; i < n; i++){
node temp;
string a, b;
cin>> a >> b;
if(a == "-"){
temp.left = -1;
}else{
temp.left = stoi(a);
isNotRoot[stoi(a)] = true;
}
if(b == "-"){
temp.right = -1;
}else{
temp.right = stoi(b);
isNotRoot[stoi(b)] = true;
}
temp.index = i;
tree[i] = temp;
}
for(int i = 0 ; i < n ; i++){
if( !isNotRoot[i] ){
root = i;
}
}
dfs(root, 1, tree);
//当最大下标等于节点数则是完全二叉树
if(maxn == n){
cout<< "YES"<<" "<<rear;
}else{
cout<< "NO"<<" "<<root;
}
return 0;
}