树的括号表述和最小表示

括号表述：遍历一棵树，每走一步记录下行走的方向，例如向远离根的方向移动记为(,向根的方向移动记为)，也可以是0和1，当然对于同一棵树这个表述不是唯一的
最小表示：树的不同括号表述中字典序最小的一种，可以用于判断两个表述是否是同一棵树的

实现

括号表述的实现很简单
将一个普通括号表述转换为最小表示的方式是进行一遍DFS，流程如下

1. DFS参数：i 用于记录当前扫到第几个字符
2. DFS返回值：S 为从该点向下的所有子树的最小表示
3. 开始DFS(0)
4. 如果S[i]为0，说明存在向下的子树，DFS(i+1)，并将返回值记录在数组中，同时i跳到扫过的子树后面
5. 直到i>len或者S[i]=1退出
6. 将数组中的字串排序，拼接并返回

代码

#include <bits/stdc++.h>
using namespace std;

string s;

string dfs(int i){
    vector <string> v;
    while (i<s.length() && s[i]=='0'){
        string t=dfs(i+1);
        v.push_back('0'+t);  //别往了加上自己
        i+=t.length()+1;
    }
    sort(v.begin(),v.end());
    string t;
    for (int i=0;i<v.size();++i) t+=v[i];
    t+='1'; //加上最后一个1
    return t;
}

void solve(){
    cin>>s;
    string a=dfs(0);
    cin>>s;
    string b=dfs(0);
    if (a==b) puts("same");
    else puts("different");
}

int main(){
    int t;
    cin>>t;
    while (t--) solve();
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/100/