关于c++:PAT甲级1110-Complete-Binary-Tree

题目粗心

给定一棵含有 N 个节点的二叉树, 判断是否是齐全二叉树

算法思路

判断一颗二叉树是否是齐全二叉树的规定：

• 1、如果呈现只有右孩子节点的，肯定不是
• 2、如果呈现只有左孩子或者没有孩子节点的，记录该状况
• 3、如果以后有孩子，并且呈现了状况 2，肯定不是
• 4、遍历树中所有节点后，如果没有 1 和 3，表明该树为齐全二叉树

遍历形式采纳层序遍历。在遍历过程中应用 count 记录遍历的节点个数，在 count= N 的时候阐明来到了最初一个节点，应用 lastNode 记录。
对于根节点的确定能够应用一个 father 数组记录每一个节点的父节点编号，初始化全副为 -1，在输出完结后，遍历一遍，第一次遇到 - 1 的编号就是根节点。

提交后果

AC 代码

#include <cstdio>
#include <iostream>
#include <queue>

using namespace std;

struct Node{
    int left = -1;
    int right = -1;
    int index{};}nodes[25];

queue<Node> que;
int lastNode;

bool isComplete(int root,int N){que.push(nodes[root]);
    bool flag = false;// 标记是否呈现状况 2
    int count = 0;
    while(!que.empty()){Node t = que.front();
        que.pop();
        ++count;
        if(count==N){
            // 最初一个节点
            lastNode = t.index;
        }
        if(t.left==-1&&t.right!=-1) {
            // 状况 1
            return false;
        }else if(t.left!=-1||t.right!=-1) {
            // 以后节点有孩子
            if(flag){return false;}
        }else if((t.left!=-1&&t.right==-1)||(t.left==-1&&t.right==-1)){
            // 只有左孩子或者没有孩子
            flag = true;
        }
        if(t.left!=-1){que.push(nodes[t.left]);
        }
        if(t.right!=-1){que.push(nodes[t.right]);
        }
    }
    return true;
}

int main() {
    int N;
    scanf("%d",&N);
    int father[N];
    for(int i=0;i<N;++i){father[i] = -1;
    }
    string left,right;
    for(int i=0;i<N;++i){
        cin>>left>>right;
        nodes[i].index = i;
        if(left!="-"){int leftChild = stoi(left);
            father[leftChild] = i;
            nodes[i].left = leftChild;
        }
        if(right!="-"){int rightChild = stoi(right);
            father[rightChild] = i;
            nodes[i].right = rightChild;
        }
    }
    int root = 0;
    for(int i=0;i<N;++i){if(father[i]==-1){
            root = i;
            break;
        }
    }
    if(isComplete(root,N)){printf("YES %d",lastNode);
    }else{printf("NO %d",root);
    }
    return 0;
}