题目链接：
http://bailian.openjudge.cn/practice/4081
4081:树的转换
总时间限制:
5000ms
单个测试点时间限制:
1000ms
内存限制:
65536kB
描述
我们都知道用“左儿子右兄弟”的方法可以将一棵一般的树转换为二叉树，如：
0 0
/ | \ /
1 2 3 ===> 1
/ \ \
4 5 2
/ \
4 3
\
5现在请你将一些一般的树用这种方法转换为二叉树，并输出转换前和转换后树的高度。
输入
输入是一个由“u”和“d”组成的字符串，表示一棵树的深度优先搜索信息。比如，dudduduudu可以用来表示上文中的左树，因为搜索过程为：0 Down to 1 Up to 0 Down to 2 Down to 4 Up to 2 Down to 5 Up to 2 Up to 0 Down to 3 Up to 0。
你可以认为每棵树的结点数至少为2，并且不超过10000。
输出
按如下格式输出转换前和转换后树的高度：
h1 => h2
其中，h1是转换前树的高度，h2是转换后树的高度。
样例输入
dudduduudu样例输出
2 => 4没有想到合适的方法去做这道题，可以用DFS去做，也可以用动态规划。
用动态规划参考别人的方法如下：
当前节点在二叉树表示中的高度=父节点高度+左兄弟数目+1
#include <iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int M=41000;//用的比较多
//神奇的题，想了很久递归去构造树，结果做不出来，下面是参考的
//使用dp来做，当前节点在二叉树表示中的高度=父节点高度+左兄弟数目+1
int h1=0,h2=0,len;
int f[M],dep[M],lch[M];//f数组是保存的上次的值，相当于对一个个字符dp
char a[M];
int main(){
cin>>a;
len=strlen(a);
int h=0;//用于循环过程中控制高度
for(int i=1;i<=len;i++){
//i其实存储的是i-1节点的信息
char tmp=a[i-1];
if(tmp=='d'){
h++;
h1=max(h1,h);
f[i]=i-1;
dep[i]=dep[i-1]+lch[i-1]+1;
//左兄弟就是父节点的左儿子
lch[i-1]++;
h2=max(h2,dep[i]);
}
else if(tmp=='u'){
h--;
f[i]=f[f[i-1]];
dep[i]=dep[f[i-1]];
lch[i]=lch[f[i-1]];
}
}
printf ("%d => %d\n",h1, h2);
}
用DFS做的方法二：
因为转换的原则和方法是左儿子右兄弟，所以可以用DFS转换，遇到d的时候就
当前节点在二叉树表示中的高度=父节点高度+左兄弟数目+1
#include <iostream>
#include <math.h>
#include <string>
using namespace std;
string s;
int res1=-1,res2=-1,i=0;
void dfs(int &i,int dep1,int dep2){
res1=max(res1,dep1);
res2=max(res2,dep2);
int cnt=0;
while(s[i]){
if(s[i]=='d'){
dfs(++i,dep1+1,dep2+cnt+1); //dep2就是父节点的高度 + 左兄弟数+1
cnt++; //记录的已经有的dfs分支 也就是左兄弟
}
else{
i++;
return;
}
}
}
int main(){
cin>>s;
dfs(i,0,0);
cout<<res1<<" => "<<res2;
return 0;
}