PAT(A) 101-145-2-2017-09-17
刷了半年题目，把练习题从头到尾都刷了一遍，看到自己位于首页，心理沾沾自喜。
今天一考，才让我看清自己到底有多菜了。。
最后一题是那种做过很多遍的建树搜索的问题。
虽然用了红黑树的背景知识，但是考的内容就是根据先序和后序建树。但是我在建树上面就花了很多时间，调试了很久，直接导致了之后时间不够。
其次在平时的练习的过程中，看到繁琐的dfs我总是想套用dijstra算法模板中枚举路径的方法。但是这道题目枚举每条路径，判断每条路径的方法是错误的。
枚举路径本质上把每条路径看成是独立的，而红黑树中这条性质
(5) For each node, all simple paths from thenode to descendant leaves contain the same number of black nodes.
是说当前节点到左子树和右子树的黑高相等，比较的是多条路径。
其实在做1103的时候，就已经暴露出这个问题的，我应该去把dfs好好看看的。
总之是我平时时候的态度导致我在知识体系上面有漏洞。
之后在学习的过程中一定要先把知识搞的特别清楚，不论这个知识到底有多繁琐，然后练习到很熟练的程度。
下面贴一下代码（这份代码可是一个点都没有通过的，贴在这里只是为了警示自己）
#include<cstdio> #include<algorithm> #include<vector> #include<cstring> #include<cmath> #include<queue> //#define debug using namespace std; const int maxn = 50; const int INF = 0x3fffffff; struct node{ int data; int lc, rc; node(){ lc = rc = -1; } }; bool cmp(int a, int b){ a = abs(a); b = abs(b); return a < b; } int Index = 0; node Tree[maxn]; int n; int PreOrder[maxn]; int InOrder[maxn]; void creat(int &root, int preL, int preR, int inL, int inR) { if (preL>preR)return; int rootE = PreOrder[preL]; root = Index++; Tree[root].data = rootE; int u = 0; for (u = inL; u <= inR; u++){ if (InOrder[u] == rootE)break; } int numLeft = u - inL; creat(Tree[root].lc, preL + 1, preL + numLeft, inL, u - 1); creat(Tree[root].rc, preL + numLeft + 1, preR, u + 1, inR); } int Bn = INF; bool IsBRt; vector<int>tpath; bool IsLegal() { int id = tpath[tpath.size() - 1]; if (Tree[id].data < 0)return false; for (int i = 1; i + 1 < tpath.size(); i++){ int id = tpath[i]; int nxt = tpath[i + 1]; if (Tree[id].data < 0 && Tree[nxt].data < 0){ return false; } } int bn = 1; for (int i = 0; i < tpath.size(); i++){ int id = tpath[i]; if (Tree[id].data> 0)bn++; } if (Bn != INF){ if (bn != Bn)return false; } else Bn = bn; return true; } void Print() { for (int i = 0; i < tpath.size(); i++){ int id = tpath[i]; printf("%d", Tree[id].data); if (i != tpath.size() - 1)printf(" "); else printf(" "); } } void dfs(int root) { if (Tree[root].lc == -1 && Tree[root].rc == -1){ tpath.push_back(root); //Print(); if (!IsLegal())IsBRt = false; tpath.pop_back(); return; } tpath.push_back(root); if (Tree[root].lc != -1) dfs(Tree[root].lc); if (Tree[root].rc != -1) dfs(Tree[root].rc); tpath.pop_back(); } void Init() { Bn = INF; tpath.clear(); IsBRt = true; Index = 0; n = 0; node t; fill(Tree, Tree + maxn, t); } int main() { #ifdef debug freopen("in.txt", "r", stdin); #endif int t; scanf("%d", &t); for (int i = 0; i < t; i++){ //注意初始化 Init(); scanf("%d", &n); for (int j = 0; j < n; j++){ scanf("%d", &PreOrder[j]); InOrder[j] = PreOrder[j]; } sort(InOrder, InOrder + n, cmp); int root; creat(root, 0, n - 1, 0, n - 1); dfs(root); if (IsBRt)printf("Yes "); else printf("No "); } #ifdef debug getchar(); #endif }