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

迷南。 2022-04-18 03:22 174阅读 0赞

Problem Description

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

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

输出二叉树的深度。  
Sample Input

2  
dbgeafc  
dgebfca  
lnixu  
linux  
Sample Output

4  
3

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    struct node
    {
        char data;
        struct node * l;
        struct node * r;
    };
    
    struct node *creat(char *a,char *b,int n)
    {
      struct node *root;
      if(n==0)
      {
          return NULL;
      }
      else
      {
          root=(struct node *)malloc(sizeof(struct node));
          root->data=b[n-1];
          int i;
          for(i=0;i<n;i++)
          {
              if(a[i]==b[n-1])
              {
                  break;
              }
          }
          int length=i;
          root->l=creat(a,b,length);
          root->r=creat(a+1+length,b+length,n-length-1);
          return root;
      }
    }
    
    int deep(struct node *root)
    {
        int n=0;
        if(root)
        {
            int l=deep(root->l);
            int r=deep(root->r);
            if(l>r)
            {
                n=l+1;
            }
            else
            {
                n=r+1;
            }
        }
        return n;
    }
    int main()
    {
       int T;
       scanf("%d",&T);
       while(T--)
       {
           char a[100];
           char b[100];
           int n;
           struct node *root;
           scanf("%s %s",a,b);
           n=strlen(a);
           root=creat(a,b,n);
           printf("%d\n",deep(root));
       }
        return 0;
    }