- 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
题目大意: 给出了红黑树的定义, 并且给出 n 组样例, 并且每一组给除了先根遍历结果, 判断每一组是否是红黑树, 红色节点用负号表示.
// 可以用先根遍历来确定一棵二叉树吗?
1. 根节点是黑色
2. 如果一个节点是黑色, 那么子节点为红色
3. 在所有从根节点到叶节点的路径上, 黑色节点的个数相同.
红黑树也是一个二叉搜索树, 所以能够根据前序来建树!!
代码转自: https://www.liuchuo.net/archives/4099
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include<cstdio>
- using namespace std;
- vector<int> arr;
- struct node {
- int val;
- struct node *left, *right;
- };
- node* build(node *root, int v) {
- if(root == NULL) {
- root = new node();
- root->val = v;
- root->left = root->right = NULL;
- } else if(abs(v) <= abs(root->val))
- root->left = build(root->left, v);// 递归建树!!!
- else
- root->right = build(root->right, v);
- return root;
- }
- bool judge1(node *root) {
- if (root == NULL) return true;
- if (root->val <0) {
- // 如果当前是红色节点, 去判断左右子树是否是黑色节点.
- if (root->left != NULL && root->left->val <0) return false;
- if (root->right != NULL && root->right->val <0) return false;
- }
- // 再递归地去判断左子节点的子数, 和右子节点的子数.
- return judge1(root->left) && judge1(root->right);
- }
- int getNum(node *root) {
- if (root == NULL) return 0;// 这里是返回个数 0.
- int l = getNum(root->left);
- int r = getNum(root->right);
- return root->val> 0 ? max(l, r) + 1 : max(l, r);
- // 如果根节点是黑节点, 那么 + 1.
- }
- bool judge2(node *root) {
- if (root == NULL) return true;
- int l = getNum(root->left);// 获取左右子树的黑节点个数.
- int r = getNum(root->right);
- if(l != r) return false;// 图三在根节点调用时在此处就会返回 false.
- return judge2(root->left) && judge2(root->right);// 再去递归判断子树中是否符合,
- // 像图二就会在这次递归中判断为 false.
- }
- int main() {
- int k, n;
- scanf("%d", &k);
- for (int i = 0; i < k; i++) {
- scanf("%d", &n);
- arr.resize(n);
- node *root = NULL;
- for (int j = 0; j < n; j++) {
- scanf("%d", &arr[j]);
- root = build(root, arr[j]);
- }
- // 如果根节点不是红色,
- if (arr[0] < 0 || judge1(root) == false || judge2(root) == false)
- printf("No\n");
- else
- printf("Yes\n");
- }
- return 0;
- }
- // 柳神真厉害.
1. 二叉树这类问题都是使用递归去做的, 掌握递归的思想十分重要.
2. 根据条件去写出函数来判断.
3. 要多复习.
来源: http://www.bubuko.com/infodetail-2850153.html