POJ 1635 Subway tree systems

题目：Some major cities have subway systems in the form of a tree, i.e. between any pair of stations, there is one and only one way of going by subway. Moreover, most of these cities have a unique central station. Imagine you are a tourist in one of these cities and you want to explore all of the subway system. You start at the central station and pick a subway line at random and jump aboard the subway car. Every time you arrive at a station, you pick one of the subway lines you have not yet travelled on. If there is none left to explore at your current station, you take the subway line back on which you first came to the station, until you eventually have travelled along all of the lines twice,once for each direction. At that point you are back at the central station. Afterwards, all you remember of the order of your exploration is whether you went further away from the central station or back towards it at any given time, i.e. you could encode your tour as a binary string, where 0 encodes taking a subway line getting you one station further away from the central station, and 1 encodes getting you one station closer to the central station. 

题目大意：在一个无环多叉树之中，从根节点出发用深度优先遍历去遍历每个元素，远离根节点用0表示；靠近根节点用1表示。现在有两个字符串，看其能否是同一颗多叉树的深度优先遍历。

思路：一棵树相同当且仅当其子树全相同；判断起来有点复杂。则弱化一下，当且仅当这两棵树的所有子树的元素个数相等，而且个数相等的子树在原树中的深度相等。例如下图：（弱化的当且仅当不知道正确与否！！没检查过是完备）

//284K  32MS
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

struct obj{
	short int len;
	short int depth;
	obj():len(0),depth(0){};
};
bool judge(string s1,string s2);//判断s1、s2是否为同一棵树的深度优先遍历
void transfor(string samp, vector<obj>& ret);//把str变成上面讲的所有子树原数个数和深度的结构数组
bool test_equ(vector<obj>& obj1,vector<obj>& obj2);//判断两个排序后的数组是否为完全相同
bool cmp(const obj &a ,const obj &b)//重载比较函数，因为要对结构体排序
{
	if(a.len < b.len)
		return true;
	if(a.len==b.len && a.depth<b.depth)
		return true;
	return false;
}
int main()
{
	const string result[2]={"different","same"};
	int num;
	string s1,s2;
	vector<obj> s12int,s22int;
	cin>>num;
	while(num--){
		s1.clear();s2.clear();
		s12int.clear();s22int.clear();
		cin>>s1>>s2;
		cout<<result[judge(s1,s2)]<<endl;
	}
//	system("pause");
	return 1;
}

bool judge(string s1,string s2){
	if(s1.size() != s2.size())
		return false;
	vector<obj> s12int,s22int;
	s12int = vector<obj>(s1.size()); transfor(s1,s12int);
	s22int = vector<obj>(s2.size()); transfor(s2,s22int);
	sort(s12int.begin(),s12int.end(),cmp);
	sort(s22int.begin(),s22int.end(),cmp);
	return test_equ(s12int,s22int);
}

void transfor(string samp, vector<obj>& ret){
	int len = samp.size(),sum,dep=0;
	if(len != ret.size())
		return;
	for(int i=0;i<len;i++){
		if(samp[i] == '1'){
			dep--;
			ret[i].depth = dep;
		}else{
			dep++;
			ret[i].depth = dep;
		}
	}
	for(int i=0;i<len;i++){
		if(samp[i]=='1'){
			ret[i].len = 0;
			continue;
		}
		sum=0;
		for(int j=i;j<len;j++){
			if(samp[j]=='1'){
				sum++;
			}else{
				sum--;
			}
			if(sum==0){
				ret[i].len = j-i+1;//可以优化，前面判断一些ret[]之后可以知道某些ret[]可以不计算
				break;
			}
		}//for(j)
	}//for(i)
}//end of fun

bool obj_equ(obj t1,obj t2){
	if((t1.depth == t2.depth) && (t1.len == t2.len))
		return true;
	return false;
}

bool test_equ(vector<obj>& obj1,vector<obj>& obj2){
	int len = obj1.size();
	for(int i=0;i<len;i++){
		if(obj_equ(obj1[i],obj2[i]) == false)
			return false;
	}
	return true;
}

遇到网上搜那个有些代码只判断子树元素个数，，没判断树深。会遇到下面的例子判断错误结果！！！但是依然能AC？！但是也不知道我的代码有没有BUG。。。
0010010111000111
0010001111001011

自己想了一下还是有问题，在处理这个示例的时候：

0010001011110000011111
0010000111110000101111

又在网上找了一下：发现有人用树的最小表示方法做。不是动态规划。就是递归将树的子树排序，然后整棵树就变成了一个有序树，然后再比较字符串就可以了。代码如下：（转至http://blog.csdn.net/u012433233/article/details/24424789）

#include <iostream>  
#include <vector>  
#include <string> 
#include <algorithm>
using namespace std;   
  
string min_pre(string str){
      vector<string> box;
      string ret = "";
      int equal = 0, st = 0;
      for(int i = 0; i < str.size(); i++){
           if(str[i] == '0') 
			   equal++;
           else 
			   equal--;
           if(equal == 0){
                if(i - 1 > st + 1){
                    box.push_back("0" + min_pre(str.substr(st + 1,i - 1 - st)) + "1");
                }else 
					box.push_back("01");
                st = i + 1;
           }
      }
      sort(box.begin(), box.end());
      for(int i = 0; i < box.size(); i++) 
		  ret += box[i];
      return ret;
} 
int main() {  
  int t;  
  cin >> t;  
  while (t--) {  
    string tree1, tree2;  
    cin >> tree1 >> tree2; 
    if (min_pre(tree1) == min_pre(tree2))  
      cout << "same" << endl;  
    else  
      cout << "different" << endl;  
  }  
  return 0;  
}