leaf 节点 simple 根据 代码 考试 span truct
红黑树的性质:
(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)null为黑,表示叶子节点(没有child的节点为叶子节点)可以为红为黑。如果条件改为null节点为红,则叶子节点必须为黑。
(4)如果该节点为红,child节点都为黑。
(5)从根节点到叶子节点的每条路径上的总black节点数都相等。
吐槽:这次PAT考试由于延考一个小时,又加上临时该题,题目出的真的不咋地,4道题目都是题意不清,全靠不断的猜和提交代码测试,才逐渐摸索出题意。
这次题目很简单,第一步根据先序遍历构造数,由于红黑树是BST树,所以已知一个先序就可以很快的构造了。第二步使用dfs来判断是否红黑树就行了。
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<string>
- #include<algorithm>
- #include<vector>
- #include<queue>
- using namespace std;
- int n,a[100];
- struct Node
- {
- int val;
- int bBlack;
- int lBlackNum;
- int rBlackNum;
- int tBlackNum;
- Node* left;
- Node* right;
- Node()
- {
- left = right = 0;
- lBlackNum = rBlackNum = tBlackNum = 0;
- }
- void setVal(int iVal)
- {
- if(iVal > 0) bBlack = 1;
- else if(iVal < 0)bBlack = 0;
- val = abs(iVal);
- }
- };
- Node* CreateTree(int l,int r)
- {
- if(l > r) return NULL;
- Node* nd = new Node();
- nd -> setVal(a[l]);
- int i = l+1;
- for(;i<=r;++i)
- if(abs(a[i]) > abs(a[l])) break;
- nd -> left = CreateTree(l+1,i-1);
- nd -> right = CreateTree(i,r);
- return nd;
- }
- void DelTree(Node **nd)
- {
- if(*nd == NULL) return;
- DelTree(&(*nd)->left);
- DelTree(&(*nd)->right);
- delete *nd;
- *nd = 0;
- }
- bool bIsTree = true;
- int lastnum = -1;
- void dfs(Node* nd,int cnt)
- {
- if(!bIsTree) return;
- if(nd == NULL)
- {
- if(lastnum == -1) lastnum = cnt;
- else if(lastnum != cnt){bIsTree = false;}
- return;
- }
- if(nd->bBlack) ++cnt;
- else
- {
- if(nd->left&&!nd->left->bBlack) bIsTree = false;
- if(nd->right&&!nd->right->bBlack) bIsTree = false;
- }
- dfs(nd->left,cnt);
- dfs(nd->right,cnt);
- }
- int main()
- {
- int t;
- scanf("%d",&t);
- while(t--)
- {
- scanf("%d",&n);
- for(int i=0;i<n;++i)
- scanf("%d",&a[i]);
- Node* root = CreateTree(0,n-1);
- bIsTree = root->bBlack;
- lastnum = -1; //初始化会忘
- dfs(root,0);
- if(bIsTree) printf("Yes\n");
- else printf("No\n");
- DelTree(&root);
- }
- return 0;
- }
PAT 1135. Is It A Red-Black Tree
来源: http://www.bubuko.com/infodetail-2313809.html