PAT(A) 1135. Is It A Red-Black Tree (30)

原题目:

原题链接:https://www.patest.cn/contests/pat-a-practise/1135

1135. Is It A Red-Black Tree (30)


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.

For example, the tree in Figure 1 is a red-black tree, while the ones in Figure 2 and 3 are not.

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:

Each input file contains several test cases. The first line gives a positive integer K (<=30) which is the total number of cases. For each case, the first line gives a positive integer N (<=30), the total number of nodes in the binary tree. The second line gives the preorder traversal sequence of the tree. While all the keys in a tree are positive integers, we use negative signs to represent red nodes. All the numbers in a line are separated by a space. The sample input cases correspond to the trees shown in Figure 1, 2 and 3.

Output Specification:

For each test case, print in a line "Yes" if the given tree is a red-black tree, or "No" if not.

Sample Input:
3
9
7 -2 1 5 -4 -11 8 14 -15
9
11 -2 1 -7 5 -4 8 14 -15
8
10 -7 5 -6 8 15 -11 17

Sample Output:
Yes
No
No

题目大意

本题看似红黑树,实际上不是,算是验证红黑树。给定树的前序遍历,负数代表黑色节点,判断是否为红黑树。

解题报告

由题:判断红黑可以有如下几个条件:

  1. 根必须时黑的。
  2. 所有红节点的孩子都是黑的。
  3. 任意节点到达其子孙叶子节点所有路径上黑色个数是相同的

题目中知道先序遍历,又因为他是平衡树,所以中序遍历也是知道的,根据这个建树,然后判断。

代码

/*
* Problem: 1135. Is It A Red-Black Tree (30)
* Author: HQ
* Time: 2018-03-13
* State: Done
* Memo: 建树,判断是否为红黑树
*/
#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;

struct Node {
    int data = 0;
    int blacknum;
    struct Node * left = NULL;
    struct Node * right = NULL;
};

int K,N;
vector<int> preOrder,inOrder;

int findIn(int x,int s,int l) {
    for (int i = 0; i < l; i++) {
        if (inOrder[s + i] == x)
            return s + i;
    }
    return -1;
}

struct Node * makeTree(int s1,int s2,int n) {
    struct Node * root = NULL;
    int pos = findIn(preOrder[s1],s2,n);
    if (pos != -1) {
        root = new struct Node;
        root->data = preOrder[s1];
        if (pos - s2 > 0)
            root->left = makeTree(s1 + 1, s2, pos - s2);
        if (s2 + n - pos - 1 > 0)
            root->right = makeTree(s1 + pos - s2 + 1, pos + 1, s2 + n - pos - 1);
    }
    return root;
}

bool cmp(int x, int y) {
    return abs(x) < abs(y);
}

bool dfs(struct 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;
    }
    bool flag = dfs(root->left) && dfs(root->right);
    if (!flag)
        return false;
    if (root->left == NULL && root->right == NULL)
        root->blacknum = (root->data > 0) ? 1 : 0;
    int l = (root->left == NULL) ? 0 : root->left->blacknum;
    int r = (root->right == NULL) ? 0 : root->right->blacknum;
    if (l != r)
        return false;
    root->blacknum = l + (root->data > 0) ? 1 : 0;
    return true;
}

bool check(struct Node * root) {
    if (root->data < 0)
        return false;
    return dfs(root);
}

int main() {
    cin >> K;
    int x;
    for (int i = 0; i < K; i++) {
        cin >> N;
        preOrder.clear();
        inOrder.clear();
        for (int j = 0; j < N; j++) {
            cin >> x;
            preOrder.push_back(x);
            inOrder.push_back(x);
        }
        sort(inOrder.begin(), inOrder.end(), cmp);
        struct Node * root = makeTree(0, 0, N);
        if (check(root))
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    system("pause");
}

发表评论

    

最新评论

    还没有人评论...

Powered by Django 2. Copyright © 2014.

huchengbei.com. All rights reserved.