1159 Structure of a Binary Tree (30 分)
抽象
学会： 1.sscanf; 2.str.find(); 3.给两个序列怎么建树（我只会一个序列建树（BST））；
PAT题目就全部链表建树吧，要的东西用map vector存。
0.main
int main(){
cin>>n;
for(int i=0;i<n;i++){
int x;
cin>>x;
post.push_back(x);
}
for(int i=0;i<n;i++){
int x;
cin>>x;
in.push_back(x);
}
root=build(n-1,0,n-1);
bfs(root,0);
cin>>m;
getchar();
for(int i=0;i<m;i++){
string a;
getline(cin,a);
if(jude(a))
printf("Yes
");
else
printf("No
");
}
return 0;
}
1.建树。
node* build(int root ,int l,int r){
//看别人都用4参数，其实没必要post的边界，只要inorder的边界
if(l>r) return NULL;
int i=0;
while(i<r && in[i]!=post[root]) i++;
node *now=new node();
now->val=post[root];
now->l=build(root-(r-i)-1,l,i-1);
now->r=build(root-1,i+1,r);
return now;
}
2.建树就老老实实建树，然后用bfs根据题目来，我是边写边看的。有一点注意， 本题额外的存储，1 map的<节点值，深度> same level 2 map的<节点值，节点值> siblings 3 map的<节点值，节点> parent child 针对不同的情况用map存，第三个不建议用数组，因为涉及左右节点的精确判断，会多敲些代码。
3.bfs,就朴素的bfs，没什么亮点。
void bfs(node*root,int de){
queue<node*> q;
root->deep=de;
q.push(root);
while(!q.empty()){
node *now=q.front();
q.pop();
mp[now->val]=now;
d[now->val]=now->deep;
int cnt=0;
if(now->l){
cnt++;
now->l->deep=now->deep+1;
q.push(now->l);
}
if(now->r){
cnt++;
now->r->deep=now->deep+1;
q.push(now->r);
}
if(now->l && now->r){
bro[now->l->val]=now->r->val;
bro[now->r->val]=now->l->val;
}
if(cnt==1) isf=0;
}
}
4.判断。大头部分， sscanf（字符串，格式，&a,&b,…）
sscanf(s.c_str(),"%d and %d are on the same level",&a,&b);
我真的第一次用。 find（)
if(s.find("root")!=-1){
sscanf(s.c_str(),"%d is the root",&a);
return a==(root->val);
}
int jude(string s){
if(s[0]==I){
return isf==1;
}
else{
int a,b;
if(s.find("root")!=-1){
sscanf(s.c_str(),"%d is the root",&a);
return a==(root->val);
}
else if(s.find("siblings")!=-1){
sscanf(s.c_str(),"%d and %d are siblings",&a,&b);
return bro[a]==b;
}
else if(s.find("level")!=-1){
sscanf(s.c_str(),"%d and %d are on the same level",&a,&b);
return d[a]==d[b];
}
else if(s.find("left")!=-1){
sscanf(s.c_str(),"%d is the left child of %d",&a,&b);
if(mp[b]->l && mp[b]->l->val==a) //这里
return 1;
}
else if(s.find("right")!=-1){
sscanf(s.c_str(),"%d is the right child of %d",&a,&b);
if(mp[b]->r && mp[b]->r->val==a) //这里
return 1;
}
else{
sscanf(s.c_str(),"%d is the parent of %d",&a,&b);
if((mp[a]->l && mp[a]->l->val==b)||(mp[a]->r && mp[a]->r->val==b)) //这里，
//这三个地方必须严格按照判断节点判断值，特别是最后个地方，我还想合起来写，结果就 段错误 。
return 1;
}
return 0;
}
}