#include<iostream> #include<stdio.h> #include<stdlib.h> #include<math.h> #include<string.h> #include<algorithm> #include<map> #include<vector> #include<queue> #include<cmath> using namespace std; vector<int> arr; struct node{ int data; struct node *left,*right; }; void insert(node* &root,int data){ if(root == NULL){//空树，查找失败，即要插入的地方 root=new node; root->data=data; root->left=root->right=NULL; return ; } if(abs(data)<=abs(root->data)) insert(root->left,data);//插在左子树 else insert(root->right,data);//插在右子树 } //判断红点(-)孩子结点是否为黑点(+) bool judge1(node *root){ if(root == NULL) return true; if(root->data<0){//如果为红点 if(root->left !=NULL && root->left->data<0) return false; if(root->right !=NULL &&root->right->data<0) return false; } return judge1(root->left)&& judge1(root->right); //递归判断左右子树 } //返回结点的树的"高度"(黑结点个数) int getNum(node *root){ if(root ==NULL) return 0; int l=getNum(root->left); int r=getNum(root->right); return root->data >0 ?max(l,r)+1 : max(l,r); } //用来检查左右孩子的高度是否相同 bool judge2(node *root){ if(root ==NULL) return true;//空树~相同 int l=getNum(root->left); int r=getNum(root->right); if(l !=r) return false; return judge2(root->left)&&judge2(root->right); } int main(){ int k,n; scanf("%d",&k);//k个树查询 for(int i=0;i<k;i++){ scanf("%d",&n); arr.resize(n); node *root=NULL; //while(1); for(int j=0;j<n;j++){ //while(1); scanf("%d", &arr[j]); //while(1); insert(root,arr[j]); //while(1); } //while(1); if(arr[0] <0 || judge1(root)==false || judge2(root)==false) printf("No\n"); else printf("Yes\n"); } system("pause"); return 0; }
错误insert如下（return问题）：
node insert(node* &root,int data){ if(root == NULL){//空树，查找失败，即要插入的地方 root=new node; root->data=data; root->left=root->right=NULL; return node; } if(abs(data)<=abs(root->data)) insert(root->left,data);//插在左子树 else insert(root->right,data);//插在右子树 }
