题目信息 1110. Complete Binary Tree (25)
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 (<=20) 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
我的代码—应该是做复杂了，看一下书再做这道题吧
#include <iostream>
#include <string>
#include <vector>
#include <exception>
using namespace std;
struct Tree{int x,y;bool p;
};
int nodes=0;
int findRoot(vector<Tree> &t)//由于根没有父节点，所以就扫了一边
{for(int i=0;i<t.size();++i){if(t.at(i).x>=0)t.at(t.at(i).x).p=true;if(t.at(i).y>=0)t.at(t.at(i).y).p=true; }//0-n-1中没有出现的就是根的indicefor(int i=0;i<t.size();++i){if(t.at(i).p==false)return i;}
}
int change(string &tmp)//解决输入问题
{try{return stoi(tmp);}catch(exception& e){return -1;}
}
//获得这棵树的高度，完全二叉树下，最后一层的个数
int getH(int nodes,int &stil)
{int tmp=1;for(int i=0;;i++){tmp=tmp*2;if(tmp>nodes){stil=nodes-tmp/2+1;return i; }}
}
int height=0;
vector<Tree>out;
bool getHe(vector<Tree>&t,int node,int h=0)
{/** 1 获取[nodes]层的所有，若不够，则不是* 2 获取[nodes]+1层的其余，若不是按序从左到右排的，则不是* 3 获取最后一个值*/bool is=true;h++;if(h<height)//height=[nodes],height-1，是满的，则height层全存在，还需判断是否连续{if(t.at(node).x==-1||t.at(node).y==-1)is= false;else{is= getHe(t,t.at(node).x,h);is= getHe(t,t.at(node).y,h);}}elseout.push_back(t.at(node));//将[nodes]一行记录return is;
}
bool isCBT(vector<Tree>&t,int root,int nodes,int &last)
{int stil=0;height=getH(nodes,stil);bool is=true;if(!getHe(t,root))return false;if(stil%2)last=out.at(stil/2).x;elselast=out.at(stil/2-1).y;//在这判断最后一层是否从左连续排列while(stil>0){if(stil%2){if(out.at(stil/2).x==-1)return false;stil--;}else{if(out.at(stil/2-1).x==-1)return false;if(out.at(stil/2-1).y==-1)return false;stil=stil-2;}}return is;
}
int main()
{string tmp;Tree ttmp;ttmp.p=false;cin>>nodes;vector<Tree> t;for(int i=0;i<nodes;i++){cin>>tmp;ttmp.x=change(tmp);cin>>tmp;ttmp.y=change(tmp);t.push_back(ttmp);}int root=findRoot(t);int num=0;if(nodes==1)//特殊情况{cout<<"YES "<<0;return 0;}if(isCBT(t,root,nodes,num))cout<<"YES "<<num;elsecout<<"NO "<<root;return 0;
}问题
- 从叶子出发还是从根出发：最终从根出发
- 怎样判断一个完全二叉树（这是关键，看完书重做这道题吧）
- 特殊情况 1 - - 输出 YES 0