学步园

用唯一性标记法，在递归建树时，给每个数分配唯一识别编号记为id  ，用map来记录（name，lson_id, rson_id）是否被标记过。

方法，很简单，但是有一点就是建树的时候遍历字符串，一定要做到o（n） ，否则超时。

下面为自己的，版本，简言之，先建树，唯一标记每棵子树，（因为序号分配是从下往上不同于题目要求，有重新转化为题目要求的编号）

#include <set>
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;

const int maxn = 1005555;
struct node{
  string c;
  int l,r;
  node(string c="0",int l=0,int r=0):
      c(c),l(l),r(r){}
  bool operator <(const node& rhs)const{
    if(c!=rhs.c){
         return c < rhs.c;
    }
    else{
        return l<rhs.l||(l==rhs.l&&r<rhs.r);
    }
  }
};
map<node,int> vis;
vector<node> idcache;
int ID(node c){
  if(vis.count(c)) return vis[c];
  idcache.push_back(c);
  return vis[c]=idcache.size();
}
typedef struct tree* pointer;
struct tree{
  int id;
  string s;
  pointer Left,Right;
  tree(string s="0",pointer x=NULL,pointer y=NULL):
      s(s),Left(x),Right(y){}
};
pointer root;
char str[maxn],src[maxn],*p;
int build(pointer& u){
  u = new tree();
  int i,cnt=0;
  u->s.clear();
  while(islower(*p)){
    u->s.push_back(*p);
    p++;
  }
  if(*p!='('){
    return u->id=ID(node(u->s,0,0));
  }
  p++;
  int num1 = build(u->Left); p++;
  int num2 = build(u->Right); p++;
  return u->id=ID(node(u->s,num1,num2) );
}
void dfs(pointer u){
  if(u->Left==NULL){
     if(vis.count(node(u->s,0,0)))
         printf("%d",vis[node(u->s,0,0)]);
     else {
        ID(node(u->s,0,0));
        cout<<u->s;
     }
     return ;
  }
  if(vis.count(node(u->s,u->Left->id,u->Right->id)))
    printf("%d",vis[node(u->s,u->Left->id,u->Right->id)]);
  else{
    cout<<u->s;
    ID(node(u->s,u->Left->id,u->Right->id));
    printf("(");
    dfs(u->Left);
    printf(",");
    dfs(u->Right);
    printf(")");
  }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%s",str);
        vis.clear();
        idcache.clear();
        p= str;
        build(root);
        vis.clear();
        idcache.clear();
        dfs(root);
        printf("\n");
    }
    return 0;
}

但是，可以用数组式建树预分配编号。若已经被访问取消预分配。

#include <set>
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;

const int maxn = 100000;
char str[maxn*5],src[maxn],*p;
struct node{
  string s;
  int left,right,ha;
  bool operator < (const node& rhs)const{
     if(ha!=rhs.ha) return ha<rhs.ha;
     else if(left!=rhs.left) return left<rhs.left;
     else return right<rhs.right;
  }
}a[maxn];
int cn=0,fu=1;
map<node,int> vis;
int build(){
  int id = cn++;
  node& u=a[id];
  u.s.clear();
  u.ha = 0;
  u.left=u.right = -1;
  while(islower(*p)){
     char c = *p;
     u.s.push_back(c);
     u.ha=u.ha*27+(c)-'a'+1;
     p++;
  }
  if(*p=='('){
    p++;
    u.left=build(); p++;
    u.right=build(); p++;
  }
  if(vis.count(u)){
      cn--;
      return vis[u];
  }
  return vis[u] = id;
}
int T,V[maxn*6];
void dfs(int id){
  if(V[id] == T) printf("%d",id+1);
  else {
     V[id] = T;
     printf("%s",a[id].s.c_str());
     if(a[id].left!=-1){
     printf("(");
     dfs(a[id].left);
     printf(",");
     dfs(a[id].right);
     printf(")");
     }
  }
}
int main()
{
    int ca;
    scanf("%d",&ca);
    for(T=1;T<=ca;T++){
        scanf("%s",str);
        cn=0;
        vis.clear();
        p = str;
        build();
        dfs(0);
        printf("\n");
    }
    return 0;
}