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

ゞ浴缸里的玫瑰 2024-02-18 22:32 73阅读 0赞

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

Time Limit: 1000 ms Memory Limit: 65536 KiB

[Submit][] [Statistic][]

Problem Description

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

Input

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

Output

输出二叉树的深度。

Sample Input

2
    dbgeafc
    dgebfca
    lnixu
    linux

Sample Output

4
    3

Hint

Source

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

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2562/pid/2804.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2562/pid/2804.html