1110 Complete Binary Tree

1110 Complete Binary Tree,第1张

题目链接
借助队列来判断是否为完全二叉树,从根节点开始将左右孩子入队,当遇到第一个空结点时终止循环,判断队列剩余部分是否还有数字,如果有则不是完全二叉树,如果没有则就是完全二叉树。
这道题有点坑的地方是编号小于等于20,即有两位数,所以子结点读取的时候要用string类型才能和“-”统一读取,如果把结点当作个位数测试点234会过不了。

#include
using namespace std;
int main(){
    int N;
    cin >> N;
    vector<vector<int> > t(N,vector<int>(2));
    vector<bool> vis(N,false);
    for(int i=0;i<N;i++){
        string a[2];
        cin >> a[0] >> a[1];
        for(int j=0;j<2;j++){
            if(a[j]=="-"){
                t[i][j]=-1;
            }else{
                int tmp=0;
                for(char c:a[j]){
                    tmp=tmp*10+c-'0';
                }
                t[i][j]=tmp;
                vis[tmp]=true;
            }
        }
        
        
    }
    int root=0;
    for(int i=0;i<N;i++){
        if(!vis[i]){
            root=i;
            break;
        }
    }
    //应该是借助队列来判断
    queue<int> q;
    q.push(root);
    int last=root;
    while(!q.empty()){
        if(q.front()==-1){
            break;
        }
        int node=q.front();
        last=node;
        q.pop();
        q.push(t[node][0]);
        q.push(t[node][1]);
    }
    //检查队列中是否都是-1
    bool f=true;
    while(!q.empty()){
        if(q.front()!=-1){
            f=false;
            break;
        }
        q.pop();
    }
    if(f){
        cout << "YES " << last;
    }else cout << "NO " << root;
    return 0;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/921857.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-16
下一篇 2022-05-16

发表评论

登录后才能评论

评论列表(0条)

保存