title: PAT1135
date: 2021-01-22 20:03:07
tags: PAT

1135

题目：

红黑树判断

范围:

1. 30个树以内
2. 每个树30个结点以内

分析:

红黑树性质

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.
   到最远叶子节点经历的黑节点数量一样

判断内容

• 根节点颜色 （坑之一很容易忘记）
• 红色节点子节点颜色
• 到叶子节点经过黑色节点数

解法:

1. 插入方式建树，结点颜色标记
2. 后序遍历树，返回两棵子树到叶子节点经历的黑色节点数
3. 若为红色节点，需要判断子节点颜色，包括子节点为空或者不为空的情况

注意事项：

在函数中我使用了指针插入树，但是实际上即使是指针也是栈里面的临时变量，需要使用引用，坑啊

代码:

#include<iostream>
#include<vector>
// #define NULL 0x00000000

enum color{
    red,
    black
};

using namespace std; 

struct node{
    int value; 
    color c; 
    node * left = NULL; 
    node * right = NULL; 
};

void insert(node * &root, node * &in_node){
    if(root == NULL) {
        root = in_node; 
        // cout<<root<<endl; 
    }
    else {
        if(root->value > in_node->value){
            insert(root->left, in_node); 
        }
        else {
            insert(root->right, in_node); 
        }
    }
    return; 
}

int visit(node *root){
    if(root == NULL) {
        // cout<<0<<endl;
        return 1; 
    }
    else{
        if(root->c == red){
            if(root->left == NULL && root->right != NULL){
                if(root->right->c == red) return -1; 
            }
            else if(root->left != NULL && root->right == NULL){
                if(root->left->c == red) return -1; 
            }
            else if(root->left != NULL && root->right != NULL){
                if(root->left->c == red || root->right->c == red) return -1; 
            }
            else return 1; 
        }
        // cout<<root->value<<endl; 
        int len_l, len_r; 
        len_l = visit(root->left);
        len_r = visit(root->right);
        // cout<<len_l<<' '<<len_r<<endl; 
        if(len_l == -1 || len_r == -1) return -1; 
        else if (len_l == len_r) {
            if(root->c == black) return len_l+1;
            else return len_l; 
        }
        else return -1; 
    } 
    
}

void delet_tree(node * root){
    if(root == NULL) return; 
    else {
        delet_tree(root->left); 
        delet_tree(root->right); 
        delete root; 
    }
}

int main(){
    freopen("./1135_in", "r", stdin); 
    int n; 
    cin>>n; 
    for(int i = 0; i < n; i++){
        int m; 
        cin>>m; 
        node * root_tmp = NULL; 
        for(int j = 0; j < m; j++){
            int tmp; 
            cin>>tmp;
            node * tmp_node_p = new node;  
            if(tmp < 0){
                tmp_node_p->c = red; 
                tmp_node_p->value = -tmp; 
            }
            else {
                tmp_node_p->c = black; 
                tmp_node_p->value = tmp; 
            }
            // cout<<tmp_node_p<<endl;
            insert(root_tmp, tmp_node_p); 
        }
        // cout<<root_tmp<<endl; 
        int ans = visit(root_tmp);
        if(root_tmp != NULL) {
            if(root_tmp->c == red) cout<<"No"<<endl; 
            else if(ans == -1) cout<<"No"<<endl; 
            else cout<<"Yes"<<endl;  
        }
        else cout<<"Yes"<<endl;  
        delet_tree(root_tmp); 
    }
}