PAT甲级1135 Is It A Red-Black Tree？【dfs】

题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805346063728640

题意：

给定一棵二叉搜索树的先序遍历结果，问这棵树是不是一棵红黑树。

思路：

首先需要明确二叉搜索树和红黑树的性质。

二叉搜索树的每个节点，左子树上的值都比这个节点的值小，右子树上的值都比这个节点的值大。

因此对于一棵二叉搜索树，如果给定了先序遍历结果，就可以唯一确定这棵树了。

红黑树的性质：

1、每个节点是红色或是黑色

2、根节点是黑色的

3、红色节点的儿子一定是黑色的

4、从任意节点到NULL指针的每一条路径的黑色节点数都是相同的

对于这道题，首先我们可以唯一的建树

然后在这棵唯一的树上进行dfs，判断当前节点的左右子树是否是一棵红黑树。边界条件显然是当节点只有一个或没有儿子的时候，此时直接判断。

【啊已经四月了！来不及了！】

 #include<cstdio>

 #include<cstdlib>

 #include<map>

 #include<set>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<cmath>

 #include<stack>

 #include<queue>

 #define inf 0x7fffffff

 using namespace std;

 typedef long long LL;

 typedef pair<string, string> pr;

 int k, n;

 const int maxn = ;

 struct node{

     int val;

     bool isred;

     int lchild, rchild;

 }nodes[maxn];

 int tot = ;

 void addnode(int val)

 {

     if(val < ){

         nodes[tot].isred = true;

         val = -val;

     }

     else{

         nodes[tot].isred = false;

     }

     nodes[tot].val = val;

     nodes[tot].lchild = nodes[tot].rchild = -;

     int now = , prev = ;

     while(now != -){

         prev = now;

         if(val > nodes[now].val){

             now = nodes[now].rchild;

         }

         else{

             now = nodes[now].lchild;

         }

     }

     if(val > nodes[prev].val){

         nodes[prev].rchild = tot++;

     }

     else{

         nodes[prev].lchild = tot++;

     }

 }

 bool flag = true;

 int dfs(int rt)

 {

     int l = nodes[rt].lchild, r = nodes[rt].rchild;

     int lres = , rres = ;

     if(l != -){

         if(dfs(l) == -)return -;

         lres += dfs(l);

     }

     if(r != -){

         if(dfs(r) == -)return -;

         rres += dfs(r);

     }

     if(l == - && r == -){

         return !nodes[rt].isred;

     }

     if(lres != rres){

         return -;

     }

     if(nodes[rt].isred && (nodes[l].isred || nodes[r].isred)){

         return -;

     }

     return lres + !nodes[rt].isred;

 }

 void printTree(int rt)

 {

     if(rt == -)return;

     printf("%d ", nodes[rt].val);

     printTree(nodes[rt].lchild);

     printTree(nodes[rt].rchild);

 }

 int main()

 {

     scanf("%d", &k);

     while(k--){

         for(int i = ; i <= tot; i++){

             nodes[tot].val = ;

             nodes[tot].isred = ;

             nodes[tot].lchild = nodes[tot].rchild = -;

         }

         tot = ;

         flag = true;

         scanf("%d", &n);

         scanf("%d", &nodes[tot].val);

         nodes[tot].isred = false;

         nodes[tot].lchild = nodes[tot].rchild = -;tot++;

         for(int i = ; i < n; i++){

             int val;

             scanf("%d", &val);

             addnode(val);

         }

         //printTree(0);

         if(nodes[].val < ){

             printf("No\n");

         }

         else{

             if(dfs() != -){

                 printf("Yes\n");

             }

             else{

                 printf("No\n");

             }

         }

     }

     return ;

 }

巴特西

PAT甲级1135 Is It A Red-Black Tree？【dfs】

最新文章

热门文章