给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。
输入格式:
输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤)和L，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列。最后L行，每行给出N个插入的元素，属于L个需要检查的序列。
简单起见，我们保证每个插入序列都是1到N的一个排列。当读到N为0时，标志输入结束，这组数据不要处理。
输出格式:
对每一组需要检查的序列，如果其生成的二叉搜索树跟对应的初始序列生成的一样，输出“Yes”，否则输出“No”。
输入样例:
4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0
输出样例:
Yes No No
C示例：
#include <stdio.h> #include <stdlib.h> typedef struct TreeNode *Tree; struct TreeNode{ int v; Tree Left,Right; int flag; }; void ResetT(Tree T){ if(T->Left) ResetT(T->Left); if(T->Right) ResetT(T->Right); T->flag = 0; } void FreeTree(Tree T){ if(T->Left) FreeTree(T->Left); if(T->Right) FreeTree(T->Right); free(T); } Tree NewNode(int V){ Tree T = (Tree)malloc(sizeof(struct TreeNode)); T->v = V; T->Left = T->Right = NULL; T->flag = 0; return T; } //向树中插入一个节点 Tree insert(Tree T,int V){ if(!T) T = NewNode(V); else{ if(V > T->v) T->Right = insert(T->Right,V); else{ T->Left = insert(T->Left,V); } } return T; } //逐个节点检查是否和比较的树一致 int Check(Tree T,int V){ if(T->flag){ if(V > T->v) return Check(T->Right,V); else if(V < T->v) return Check(T->Left,V); else return 0; } else{ if(V == T->v){ T->flag = 1; return 1; } else return 0; } } //判断树是否相同 int Judge(Tree T,int N){ int i,V; //增加一个判断当前树的标记 0表示一致 1表示不一致 int flag=0; scanf("%d",&V); if(T->v != V) flag=1; else T->flag = 1; for(i=1;i<N;i++){ scanf("%d",&V); if(!flag && !Check(T,V)) flag=1; } if(flag) return 0; else return 1; } //创建树 Tree MakeTree(int N){ Tree T; int i,V; scanf("%d",&V); T = NewNode(V); for(i=1;i<N;i++){ scanf("%d",&V); T = insert(T,V); } return T; } int main(){ int N,L,i; Tree T; //读取数据 scanf("%d",&N); while(N){ scanf("%d",&L); T = MakeTree(N); //取后面的数据来和第一个数对比判断 for(i=0;i<L;i++){ if(Judge(T,N)) printf("Yes "); else printf("No "); //清除flag标记 ResetT(T); } FreeTree(T); scanf("%d",&N); } return 0; }