PAT 1135 Is It A Red-Black Tree
There is a kind of balanced binary search tree named red-black tree in the data structure. It has the following 5 properties: (1) Every node is either red or black. (2) The root is black. (3) Every leaf (NULL) is black. (4) If a node is red,then both its children are black. (5) For each node,all simple paths from the node to descendant leaves contain the same number of black nodes. Figure 1 Figure 2 Figure 3 For each given binary search tree,you are supposed to tell if it is a legal red-black tree. Input Specification: Output Specification: Sample Input:
Sample Output:
#include<iostream> //偏难 #include<vector> #include<math.h> using namespace std; struct node{ int val; node* left; node* right; node(int v):val(v),left(NULL),right(NULL){ } }; vector<int> a,pre; int cnt=0,flag=0; node* buildtree(node* t,int b,int e){ if(b>e) return NULL; t=new node(a[b]); int i=b+1; while(i<=e&&abs(a[i])<abs(a[b])) i++; t->left=buildtree(t->left,b+1,i-1); t->right=buildtree(t->right,i,e); return t; } bool isBTree(node* root,int num){ if(!root) if(num!=cnt) return false; else return true; if(root->val>0) num++; else{ if(root->right&&root->right->val<0) return false; if(root->left&&root->left->val<0) return false; } return isBTree(root->left,num)&&isBTree(root->right,num); } int main(){ int k,n; cin>>k; for(int i=0; i<k; i++){ cin>>n; a.clear(); a.resize(n); cnt=0; for(int j=0; j<n; j++) cin>>a[j]; node* root=NULL; root=buildtree(root,n-1); node* temp=root; while(temp){ cnt=(temp->val>0?cnt+1:cnt); temp=temp->left; } if(isBTree(root,0)&&root->val>0) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |