OpenJ_Bailian 4081 树的转换 数据结构

题目：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=412663

题意：

我们都知道用“左儿子右兄弟”的方法可以将一棵一般的树转换为二叉树，如：

    0                             0
  / | \                          /
 1  2  3       ===>             1
   / \                           \
  4   5                           2
                                 / \
                                4   3
                                 \
                                  5

现在请你将一些一般的树用这种方法转换为二叉树，并输出转换前和转换后树的高度。

Input

输入是一个由“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。

Output

按如下格式输出转换前和转换后树的高度：
h1 => h2
其中，h1是转换前树的高度，h2是转换后树的高度。

Sample Input

dudduduudu

Sample Output

2 => 4

思路：刚开始想的是构造一个二叉树，后来想想并不需要，了解树转二叉树的原理，便可以发现转换后某点的深度为父节点的深度加上它是父节点的第几个子节点，所以直接从根节点按以上规律搜索一遍即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <functional>
#include <cctype>
#include <cmath>
using namespace std;

const int N = 100100;
char s[N];
int res1, res2;
void dfs(int &i, int dep1, int dep2)
{
    res1 = max(res1, dep1);
    res2 = max(res2, dep2);
    int cnt  = 1;
    while(true && s[i])
    {
        if(s[i] == 'd')
            dfs(++i, dep1 + 1, dep2 + cnt), cnt++;
        else
        {
            i++;
            return;
        }
    }
}
int main()
{
    while(~ scanf(" %s", s))
    {
        int i = 0;
        res1 = res2 = -1;
        dfs(i, 0, 0);
        printf("%d => %d\n", res1, res2);
    }
    return 0;
}