POJ-1635:Subway tree systems（树的最小表示法）

题目链接：点击打开链接

题目大意：

给你两个用01串表示的树，0表示向下进一个节点，1表示回到上一个节点，走过的节点不再走。问两颗树是否同构。

树的同构有点难解释，不过把样例画出来应该就没啥问题了。

解题思路：

刚开始完全不会写，对树真的一点感觉都没有。后来想到可能是把树尽量搞成一样的样子，大概就是将子节点有序的排好。最后重新用01表示，但是不会实现。

后来看了大佬的代码，实现的好强。。。反正自己对dfs一点感觉都没有。。。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#define next ne
using namespace std;
typedef long long ll;
int INF=1e9+7;
int n,ans,maxlen;
char s[10010];

string solve(int l,int r)
{
    vector<string> v;
    int cnt=0,p=l;
    for(int i=l;i<=r;i++)
    {
        if(s[i]=='0')
            cnt++;
        else
            cnt--;
        if(cnt==0)
        {
            v.push_back(solve(p+1,i-1));    //当发现重新回到当前节点就递归进入这个节点
            p=i+1;
        }
    }
    sort(v.begin(),v.end());    //将节点按个数排序
    string re="0";
    for(int i=0;i<(int)v.size();i++)    //构造新的表示方法
        re=re+v[i];
    return re+"1";
}
int main()
{
    int QAQ;
    scanf("%d",&QAQ);
    while(QAQ--)
    {
        int l;
        scanf(" %s",s);
        l=strlen(s);
        string a=solve(0,l-1);
        scanf(" %s",s);
        l=strlen(s);
        string b=solve(0,l-1);
        if(a==b)
            printf("samen");
        else
            printf("differentn");
    }
}

最后

以上就是欣慰云朵为你收集整理的POJ-1635:Subway tree systems（树的最小表示法）的全部内容，希望文章能够帮你解决POJ-1635:Subway tree systems（树的最小表示法）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。