2804 数据结构实验之二叉树八：（中序后序）求二叉树的深度

雨点打透心脏的1/2处 2022-06-04 23:35 141阅读 0赞

### 数据结构实验之二叉树八：（中序后序）求二叉树的深度 ###

Time Limit: 1000MS  Memory Limit: 65536KB

#### Problem Description ####

已知一颗二叉树的中序遍历序列和后序遍历序列，求二叉树的深度。

#### Input ####

输入数据有多组，输入T，代表有T组数据。每组数据包括两个长度小于50的字符串，第一个字符串表示二叉树的中序遍历，第二个表示二叉树的后序遍历。

#### Output ####

输出二叉树的深度。

#### Example Input ####

2
    dbgeafc
    dgebfca
    lnixu
    linux

#### Example Output ####

4
    3

#include <bits/stdc++.h>
    using namespace std;
    
    struct node
    {
        char data;
        struct node *l,*r;
    };
    struct node *build(char *a,char *b,int n)
    {
        int i;
        struct node *root;
        if(n==0){return NULL;}
        for(i=0;i<n;i++)
        {
            if(a[i]==b[n-1])break;
        }
        root = new struct node;
        root ->data = b[n-1];
        root ->l = build(a,b,i);
        root ->r = build(a+1+i,b+i,n-1-i);
        return root;
    }
    int deep(struct node *root)
    {
        if(root==NULL) return 0;
        else
        {
            return max(deep(root->l),deep(root->r))+1;
        }
    }
    
    int main()
    {
        int t,n;
        char a[100],b[100];
        struct node *root;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%s",a);
            scanf("%s",b);
            n = strlen(a);
            root = build(a,b,n);
            printf("%d\n",deep(root));
        }
        return 0;
    }