- Given a tree, you are supposed to tell if it is a complete binary tree.
- Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤) which is the total number of nodes in the tree -- and hence the nodes are numbered from 0 to N−1. Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a - will be put at the position. Any pair of children are separated by a space.
- Output Specification:
- For each case, print in one line YES and the index of the last node if the tree is a complete binary tree, or NO and the index of the root if not. There must be exactly one space separating the Word and the number.
- 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
- /*
- 思路是先建树, 找根节点, 先序遍历找到最大节点, 如果等于 n 表示完全二叉树
- */
- #include<iostream>
- #include<cstdlib>
- using namespace std;
- const int maxn = 21;
- bool isRoot[maxn] = {0};
- int max_index = -1,last_v;
- int root = 0;
- struct Node
- {
- int left,right;
- }node[maxn];
- int getNum(string s)
- {
- int iRet = -1;
- if(s != "-")
- {
- iRet = atoi(s.c_str());
- isRoot[iRet] = 1;
- }
- return iRet;
- }
- void FindRoot(int n)
- {
- for(int i = 0; i <n; i++)
- {
- if(0 == isRoot[i])
- {
- root = i;
- break;
- }
- }
- }
- void preOrder(int v,int index)
- {
- if(-1 == v)
- {
- return;
- }
- if(index> max_index)
- {
- max_index = index;
- last_v = v;
- }
- preOrder(node[v].left,index*2);
- preOrder(node[v].right,index*2+1);
- }
- int main()
- {
- int n;
- cin>> n;
- string s1,s2;
- for(int i = 0; i <n; i++)
- {
- cin>> s1>> s2;
- node[i].left = getNum(s1);
- node[i].right = getNum(s2);
- }
- FindRoot(n);
- preOrder(root,1);
- if(max_index == n)
- {
- printf("YES %d",last_v);
- }
- else
- {
- printf("NO %d",root);
- }
- return 0;
- }
下面版本三个点段错误, 待查
- #include<cstdio>
- const int maxn = 30;
- struct Node
- {
- int left,right;
- }node[maxn];
- int max_index = -1,last_v;
- bool isRoot[maxn] = {0};
- int root;
- int changeNum(char c)
- {
- int iRet = -1;
- if(c != '-')
- {
- iRet = c - '0';
- isRoot[iRet] = 1;
- }
- return iRet;
- }
- void FindRoot(int n)
- {
- for(int i = 0; i <n; i++)
- {
- if(0 == isRoot[i])
- {
- root = i;
- break;
- }
- }
- }
- void preOrder(int v,int index)
- {
- if(-1 == v)
- {
- return;
- }
- if(index> max_index)
- {
- max_index = index;
- last_v = v;
- }
- preOrder(node[v].left,index*2);
- preOrder(node[v].right,index*2+1);
- }
- int main()
- {
- int n;
- scanf("%d",&n);
- char c1,c2;
- for(int i = 0; i < n; i++)
- {
- getchar();
- scanf("%c%*c%c",&c1,&c2);
- node[i].left = changeNum(c1);
- node[i].right = changeNum(c2);
- }
- FindRoot(n);
- preOrder(root,1);
- if(max_index == n)
- {
- printf("YES %d",last_v);
- }
- else
- {
- printf("NO %d",root);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3111358.html