1110 Complete Binary Tree（完全二叉树）

痛定思痛。 2021-12-20 23:11 183阅读 0赞

### 题意： ###

给出一个n表示有n个结点，这n个结点为0~n-1，给出这n个结点的左右孩子，求问这棵树是不是完全二叉树

### 思路： ###

这题就是先建树，找出根结点然后层序遍历，我一开始是把每层的结点数存储下来看是否等于2^i，结果有两个案例没过，看别人的代码有更好的方法，就是记录遍历的个数cnt，如果遇到空结点并且(cnt==n)那就是完全二叉树，如果(cnt!=n)那就不是完全二叉树。注意会存在一开始cnt!=n而后来cnt==n的情况，所以只取第一次cnt!=n的情况，可以设立一个bool值判断。

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 50;
    int n;
    
    struct node {
    	int left, right;
    	int pre=-1;
    }tree[maxn];
    
    int main() {
    	scanf("%d", &n);
    	for (int i = 0; i < n; i++) {
    		string u, v;
    		cin >> u >> v;
    		if (u == "-") {
    			tree[i].left = -1;
    		} else {
    			int uu = stoi(u);
    			tree[i].left = uu;
    			tree[uu].pre = i;
    		}
    		if (v == "-") {
    			tree[i].right = -1;
    		} else {
    			int vv = stoi(v);
    			tree[i].right = vv;
    			tree[vv].pre = i;
    		}
    	}
    	int root = 0;
    	for (; tree[root].pre != -1; root = tree[root].pre);
    	queue<int> que;
    	que.push(root);
    	int cnt = 0,lastnode=0;
    	while (!que.empty()) {
    		int u = que.front(); que.pop();
    		if (u != -1) {
    			lastnode = u;
    			cnt++;
    		} else {
    			if (cnt != n) {
    				printf("NO %d", root);
    			} else {
    				printf("YES %d", lastnode);
    			}
    			return 0;
    		}
    		que.push(tree[u].left);
    		que.push(tree[u].right);
    	}
    	return 0;
    }

转载于:https://www.cnblogs.com/seasonal/p/10343603.html