二叉搜索树的后序遍历序列
-
- #include <stdio.h>
-
- int seq[10005];
- bool valid(int x, int y)
- {
- if(x >= y)
- return true;
-
- int i=y-1;
- while(i>=x && seq[i]>seq[y])
- {
- --i;
- }
- int j = i;
- while(i>=x && seq[i]<seq[y])
- {
- --i;
- }
- if(i>=x)
- return false;
-
- if(!valid(x, j))
- return false;
-
- if(!valid(j+1, y-1))
- return false;
-
- return true;
- }
-
- int main(void)
- {
- int n;
- while(scanf("%d", &n) == 1)
- {
- for(int i=0; i<n; ++i)
- scanf("%d", &seq[i]);
-
- if(valid(0, n-1))
- printf("Yes\\n");
- else
- printf("No\\n");
- }
-
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/050720134451.html