文章目录

• 前言
• 1110 Complete Binary Tree (25 分)
• • 分析
  • AC代码
  • 简化
• 总结

前言

今日完成任务：
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;
}

总结