一、题目描述

原题链接 Given a tree, you are supposed to tell if it is a complete binary tree.

Input Specification:

​​Output Specification:

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

二、解题思路

完全二叉树填入数组之后，父亲结点和左右孩子的编号是有特定关系的（两倍或两倍加1），利用这个关系，我们只需要看dfs遍历出来的最大编号等不等于N-1就可以知道是否为完全二叉树。

三、AC代码

#include<iostream> #include<cstdio> #include<vector> #include<queue> using namespace std; struct Node { int id, parent=-1, left, right; }node[25]; int maxn = -1, ans; void dfs(int root, int index) //dfs，求出如果是完全二叉树最后一个结点的编号 { if(index > maxn) { maxn = index; ans = root; } if(node[root].left != -1) dfs(node[root].left, index*2+1); if(node[root].right != -1) dfs(node[root].right, index*2+2); return; } bool check(string str) { for(int i=0; i<str.size(); i++) { if(str[i] == '-') return false; } return true; } int main() { int N; string ch1, ch2; scanf("%d", &N); for(int i=0; i<N; i++) { getchar(); cin >> ch1 >> ch2; node[i].id = i; node[i].left = check(ch1) ? stoi(ch1) : -1; node[i].right = check(ch2) ? stoi(ch2) : -1; if(node[i].left != -1) node[node[i].left].parent = i; if(node[i].right != -1) node[node[i].right].parent = i; } Node root; for(int i=0; i<N; i++) { if(node[i].parent == -1) //parent==-1则为根结点 root = node[i]; } dfs(root.id, 0); bool flag = true; if(maxn != N-1) flag = false; //如果最后一个元素的编号不是N-1，则不是完全二叉树 flag ? printf("YES %d", ans) : printf("NO %d", root.id); return 0; }