乐趣区

关于算法-数据结构:PAT甲级1135-Is-It-A-RedBlack-Tree

题目粗心:

给定 K 给测试用例,每一个测试用例给定一个 N 个结点的二叉搜寻树的前序序列,要求判断该二叉树是否是红黑树。

算法思路:

首先应用 isRed 记录所有的红色结点,这样在建树的时候就能够应用负数来建树。而后再依据先序序列建设二叉搜寻树(不须要中序), 而后再应用先序遍历判断该数是否是红黑树即可。

建树过程:

每一次递归拜访首先建设根节点并初始化数据,而后找到第一个大于根节点的地位 k,这样 [preL+1,k-1] 为左子树,[k,preR]为右子树,别离递归建树就好。

Node* createTree(int preL,int preR){if(preL>preR) return nullptr;
    Node *root = new Node;
    root->data = pre[preL];
    // 找到第一个大于根节点的地位 k
    int k;
    for(k=preL+1;k<=preR;++k){if(pre[k]>root->data) break;
    } 
    // [preL+1,k-1]为左子树
    root->left =  createTree(preL+1,k-1);
    // [k,preR]为右子树
    root->right = createTree(k,preR);
    return root;
}
先序遍历判断过程:

如果 root==nullptr,阐明达到叶子结点,将以后门路彩色结点数目 countBlack 增加进 set cntBlack 中,而后判断汇合大小是否为 1,如果不是阐明不是红黑树。如果不是叶子结点,就拜访该结点,如果是彩色结点,就自增 countBlack,如果是红色结点,就判断其存在的孩子是否也是红色结点,如果是就阐明不是红黑树,并返回,否则就递归拜访左子树和右子树。

unordered_set<int> cntBlack;// 记录每一条门路的彩色结点个数
void DFS(Node *root,int countBlack,bool &flag){if(root==nullptr){
        // 达到叶子结点 
        cntBlack.insert(countBlack);
        if(cntBlack.size()!=1){
            // 呈现不同门路彩色结点不同的状况 
            flag = false;
        }
        return;
    }
    // 以后结点为黑结点 
    if(!isRed[root->data]){++countBlack;}else {
        // 以后结点为红结点
        if((root->left!=nullptr&&isRed[root->left->data])||(root->right!=nullptr&&isRed[root->right->data])) {
            // 孩子结点也为红色 
            flag = false;
            return;
        }
    }
    DFS(root->left,countBlack,flag);
    DFS(root->right,countBlack,flag);
}

在建树之前,先判断根节点是否是彩色结点,如果是再建树,能够缩小工夫老本。

留神点:

  • 1、这里须要对于第三条须要顺便阐明一下,叶子结点为空是不是黑的不重要,重要的是肯定得搜寻到空再判断以后门路的彩色结点数目是否统一,否则会呈现判断不齐全,因为从根节点到 NULL 和到非空叶子结点的门路不齐全一样(前者蕴含后者),本人入手将 NULL 补全,画进去就晓得了。
  • 2、对于测试点 3 呈现的段谬误,个别是 2 个起因,第一个是开拓的数组太小,最小为 3225。第二是建树的时候呈现内存透露,比方没有写 return;,也有可能是采纳了不失当的建树形式(我间接采纳前序和中序建树就呈现段谬误,改为前序建树就好了)。
  • 3、每一次查问都得初始化全局变量。

提交后果:

AC 代码:

#include<cstdio>
#include<vector>
#include<cstring>
#include<unordered_set>

using namespace std;

struct Node{
    int data;
    Node *left;
    Node *right;
};

const int maxn = 3225;// 通过测试,最小为 3225,否则测试点 3 段谬误 
bool isRed[maxn];// 记录结点是否是红色的 
int pre[maxn];// 前驱序列 
unordered_set<int> cntBlack;// 记录每一条门路的彩色结点个数 

Node* createTree(int preL,int preR){if(preL>preR) return nullptr;
    Node *root = new Node;
    root->data = pre[preL];
    // 找到第一个大于根节点的地位 k
    int k;
    for(k=preL+1;k<=preR;++k){if(pre[k]>root->data) break;
    } 
    // [preL+1,k-1]为左子树
    root->left =  createTree(preL+1,k-1);
    // [k,preR]为右子树
    root->right = createTree(k,preR);
    return root;
}

void DFS(Node *root,int countBlack,bool &flag){if(root==nullptr){
        // 达到叶子结点 
        cntBlack.insert(countBlack);
        if(cntBlack.size()!=1){
            // 呈现不同门路彩色结点不同的状况 
            flag = false;
        }
        return;
    }
    // 以后结点为黑结点 
    if(!isRed[root->data]){++countBlack;}else {
        // 以后结点为红结点
        if((root->left!=nullptr&&isRed[root->left->data])||(root->right!=nullptr&&isRed[root->right->data])) {
            // 孩子结点也为红色 
            flag = false;
            return;
        }
    }
    DFS(root->left,countBlack,flag);
    DFS(root->right,countBlack,flag);
}

int main(){
    int K,N;
    scanf("%d",&K);
    for(int i=0;i<K;++i){memset(isRed,0,sizeof(isRed));
        cntBlack.clear();
        scanf("%d",&N);
        bool isRedBlackTree = true;
        for(int j=0;j<N;++j){scanf("%d",&pre[j]);
            if(pre[j]<0){pre[j] = -pre[j];
                isRed

] = true;
}
}
// 根节点是红色结点肯定不是红黑树
if(isRed


]) {
isRedBlackTree = false;
printf("No\n");
}else{
// 依据前序遍历构建二叉搜寻树
Node *root = createTree(0,N-1);
// 先序遍历判断以后树是否是红黑树
DFS(root,0,isRedBlackTree);
if(isRedBlackTree){
printf("Yes\n");
}else{
printf("No\n");
}
}
}
return 0;
}


退出移动版