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

爱被打了一巴掌 2022-05-31 01:42 123阅读 0赞

数据结构实验之二叉树八：（中序后序）求二叉树的深度  
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

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    struct node
    {
        char data;
        struct node *l, *r;
    };
    
    int max(int a, int b)
    {
        if(a > b) return a;
        else return b;
    }
    
    struct node *creat(char *s1, char *s2, int n)
    {
        int i;
        if(n == 0)
            return NULL;
        else
        {
            struct node *root;
            root = (struct node*) malloc (sizeof(struct node));
            root -> data = s2[n - 1];
            for(i = 0; i < n; i++)
            {
                if(s1[i] == s2[n - 1])
                    break;
            }
            root -> l = creat(s1, s2, i);
            root -> r = creat(s1 + i + 1, s2 + i, n - i - 1);
            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;
        scanf("%d", &t);
        while(t--)
        {
            char s1[60], s2[60];
            int len;
            scanf("%s", s1);
            scanf("%s", s2);
            len = strlen(s1);
            struct node *root;
            root = creat(s1, s2, len);
            printf("%d\n", deep(root));
        }
        return 0;
    }