PAT 1135 Is It A Red-Black Tree

这一题的大意是给出一个二叉搜索树，让我们判断是不是红黑树，
只需要按题目要求构造好树，然后判断它是不是符合红黑树的条件即可。
题目给出了红黑树的性质，我们只需要判断它是否满足即可。
需要我们对二叉搜索树，建树，DFS掌握好
完整代码如下：

#include<bits/stdc++.h>#include<iostream>usingnamespacestd;//构造一棵二叉搜索树structnode{intdata;structnode*l;structnode*r;intcolor;};node*tostruct_tree(node*root,intx){if(root==nullptr){root=new(node);root->data=x;if(x>0){root->color=1;//表示黑色}else{root->color=0;//表示红色}root->l=nullptr;root->r=nullptr;}elseif(abs(x)<abs(root->data)){root->l=tostruct_tree(root->l,x);}elseif(abs(x)>abs(root->data)){root->r=tostruct_tree(root->r,x);}returnroot;}intgetBlackHeight(node*x){if(x==nullptr)return1;// NULL节点视为黑色（属性3）// 递归获取左右子树黑高intleft=getBlackHeight(x->l);intright=getBlackHeight(x->r);if(left==-1||right==-1)return-1;// 下层已经发现不合法，继续上传if(left!=right)return-1;// 属性5不满足，黑高不一致// 若当前是黑节点，黑高 +1returnleft+(x->color==1?1:0);}boolisredtree(node*root,boolflag){if(flag==0){if(root->color==0){returnfalse;}flag=1;}if(root!=nullptr&&root->color==0){//红色if(root->l!=nullptr&&root->l->color==0){returnfalse;}if(root->r!=nullptr&&root->r->color==0){returnfalse;}}if(getBlackHeight(root)==-1)returnfalse;if(root->l!=nullptr){if(!isredtree(root->l,1)){// cout<<"1"<<endl;returnfalse;}}if(root->r!=nullptr){if(!isredtree(root->r,1)){returnfalse;}}returntrue;}intmain(){intK;cin>>K;for(inti=0;i<K;i++){intN;cin>>N;node*root=nullptr;for(intj=0;j<N;j++){intx;cin>>x;root=tostruct_tree(root,x);}boolflag=0;if(isredtree(root,flag)){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}return0;}

总结：考察树的相关性质，对基本知识点掌握扎实就好做。注意题目要求，我刚开始就自己幻想出多余条件，和理解错题意而写错，在写代码的时候也难免会写出bug，需要有较强的debug能力。