题目粗心

给定一棵含有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;}