SDUT-2804 데이터 구조 실험의 2차원 트리 8: (중차순 후차순) 2차원 트리의 깊이를 구하기

데이터 구조 실험의 두 갈래 나무 8: (중차원 후차원) 두 갈래 나무의 깊이를 구한다


Time Limit: 1000MS 
Memory Limit: 65536KB
Submit  Statistic

Problem Description


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

Input


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

Output


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

Example Input

2
dbgeafc
dgebfca
lnixu
linux

Example Output

4
3

Hint


Author


 
#include 
#include 
using namespace std;
struct Btree
{
    Btree*left;
    Btree*right;
    char data;
};
string s1,s2;
Btree*build(string s1,string s2,int n)
{
    int i;
    if(n==0)
        return NULL;
    Btree*root;
    root=new Btree;
    root->data=s2[n-1];
    for(i=0; idata)
        {
            break;
        }
    }
    root->left=build(s1,s2,i);
    root->right=build(s1.substr(1+i),s2.substr(i),n-1-i);//ss=s.substr(start,(N));ss=s.substring(start,end); 
    return root;
}
int Depth(Btree*root)
{
    if(root==NULL)
        return 0;
    else
    {
        int n1,n2;
        n1=Depth(root->left);
        n2=Depth(root->right);
        return n1>n2?n1+1:n2+1;// n1+1 n2+1 
    }
}
int main()
{
    int n,T;
    while(cin>>T)
    {
        while(T--)
        {
            Btree*root;
            cin>>s1;
            cin>>s2;
            n=s1.size();
            root=build(s1,s2,n);
            int d=Depth(root);
            cout<

좋은 웹페이지 즐겨찾기