AcWing 1628. 判断红黑树
原题链接
中等
作者:
leo123456
,
2020-08-23 14:52:44
,
所有人可见
,
阅读 1151
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N=40;
int pre[N],in[N];
unordered_map<int,int> pos;
bool ans;
int build(int il,int ir,int pl,int pr,int& sum)
{
int root=pre[pl];
int k=pos[abs(root)]; //中序遍历是按从小到大去掉符号排序的,root从pre找的可以是负数
if(k<il||k>ir) //每次建树不放心,这个条件可以都写上,保险
{
ans=false;
return 0;
}
int left=0,right=0,ls=0,rs=0; //左,右子路上黑色结点数
if(il<k) left=build(il,k-1,pl+1,pl+1+(k-1-il),ls);
if(k<ir) right=build(k+1,ir,pl+1+(k-1-il)+1,pr,rs);
if(ls!=rs) ans=false;
sum=ls; //因为sum是返回上一层的,所以两条子路上的相同,随便赋值一个,
if(root<0)
{
if(left<0||right<0) ans=false; //如果当前结点是红色,看看它的子节点是否是黑色,不是就false
}
else sum++; //如果当前结点是黑色,则它到子结点的黑色数目等于,子路上的+它一个
return root;
}
int main()
{
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>pre[i];
in[i]=abs(pre[i]);
}
sort(in,in+n);
pos.clear(); //多组测试数据,每次都要先清空上次的残留
for(int i=0;i<n;i++) pos[in[i]]=i;
ans=true;
int sum; //从当前结点到叶子结点上的黑色结点数目
int root=build(0,n-1,0,n-1,sum);
if(root<0) ans=false;
if(ans) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
if(il<k) left=build(il,k-1,pl+1,pl+1+(k-1-il),ls);
这个为什么要价格判断啊?
为什么
il<=k
不行呢因为如果il==k的话,左子树是空树,空树的root一定是0,上面已经初始化过了,所以不需要再判断