sdutoj2804 두 갈래 나무의 깊이를 구하기 (중순 및 후순에 따라 트리를 반복 구하기)

제목 링크: 링크 열기 클릭

두 갈래 나무의 깊이를 구하다



Time Limit: 1000MS Memory limit: 65536K


제목 설명


이미 알고 있는 두 갈래 나무의 중차적 역행 서열과 후차적 역행 서열은 두 갈래 나무의 깊이를 구한다.

입력


입력 데이터가 여러 그룹, 입력 T는 T그룹 데이터가 있음을 나타냅니다.각 그룹의 데이터는 길이가 50보다 작은 두 개의 문자열을 포함하는데, 첫 번째 문자열은 두 갈래 나무의 중차적 이동을 나타내고, 두 번째 문자열은 두 갈래 나무의 후차적 이동을 나타낸다.

출력


두 갈래 나무의 깊이를 출력합니다.

예제 입력

2
dbgeafc
dgebfca
lnixu
linux

예제 출력

4
3

힌트


 
코드 구현:
#include 
#include 
#include 
#include 
using namespace std;

struct Tree
{
    char data;
    Tree *lchild,*rchild;
};

char a[110],b[110];

/// 
Tree *Creat(int n,char a[],char b[])
{
    if(n == 0)
        return NULL;
    char *p;
    Tree *T;
    T = new Tree;
    T->data = b[n - 1];/// 
    for(p = a; *p != '\0'; p++)/// 
    {
        if(*p == b[n - 1])
            break;
    }
    int t = p - a;
    T->lchild = Creat(t,a,b);/// , 
    T->rchild = Creat(n - t - 1,p + 1,b + t);/// , 
    return T;
}

int Depth(Tree *T)
{
    int ldepth,rdepth;
    if(!T)
        return 0;
    else
    {
        ldepth = Depth(T->lchild);
        rdepth = Depth(T->rchild);
        return ldepth > rdepth ? ldepth+1 : rdepth+1;
    }
}

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        while(n--)
        {
            memset(a,0,sizeof(a));
            memset(b,0,sizeof(b));
            Tree *T;
            scanf("%s%s",a,b);
            int len = strlen(a);
            T = Creat(len,a,b);
            printf("%d
",Depth(T)); } } return 0; }

좋은 웹페이지 즐겨찾기