题意：给出2个深搜过程，确定是否是对同一棵树的遍历。深搜过程是用01串来描述的，0代表远离树根，1代表靠近树根。
分析：利用最小表示的思想，我们将树的所有结点按一定的规则排个序，然后比较2棵树的结点是否一样即可。排序规则：先按深度排序（离树根的距离），深度相同的按以该结点为根的子树结点数目排序。其实排序的过程就是统一遍历规则的过程，利用上面的规则排序后的结点是一个宽度优先的搜索顺序，且同一层中按后代结点数目小的先遍历。
View Code
#include <stdio.h> #include <stdlib.h> #include <string.h> #define N 3010 struct node { int dep,son; }; node tree1[N],tree2[N]; char s[N]; int len1,len2; int cmp(const void *a,const void *b) { node *c=(node*)a; node *d=(node*)b; if(c->dep==d->dep) return c->son-d->son; return c->dep-d->dep; } void init() { memset(tree1,0x3f,sizeof(tree1)); memset(tree2,0x3f,sizeof(tree2)); } void build(node *tree,char *s) { int i,j,dep=0; for(i=0;s[i];i++) { if(s[i]=='0') { dep++; tree[i].dep=dep; int cnt=1,son=0; for(j=i+1;cnt && s[j];j++) { if(s[j]=='0') cnt++,son++; if(s[j]=='1') cnt--; } tree[i].son=son; } else dep--; } } void solve() { qsort(tree1,len1,sizeof(tree1[0]),cmp); qsort(tree2,len2,sizeof(tree2[0]),cmp); int i; for(i=0;tree1[i].dep<len1;i++) { if(tree1[i].dep^tree2[i].dep) break; if(tree1[i].son^tree2[i].son) break; } if(tree1[i].dep<len1 || (len1^len2)) puts("different"); else puts("same"); } int main() { int t; scanf("%d",&t); while(t--) { init(); scanf("%s",s); len1=strlen(s); build(tree1,s); scanf("%s",s); len2=strlen(s); build(tree2,s); solve(); } return 0; }