数据结构实验之二叉树四：还原二叉树

痛定思痛。 2022-07-12 07:21 141阅读 0赞

数据结构实验之二叉树四：还原二叉树  
Time Limit: 1000MS Memory Limit: 65536KB  
Submit Statistic  
Problem Description

给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。  
Input

输入数据有多组，每组数据第一行输入1个正整数N(1 <= N <= 50)为树中结点总数，随后2行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母(区分大小写)的字符串。  
Output

输出一个整数，即该二叉树的高度。  
Example Input

9  
ABDFGHIEC  
FDHGIBEAC  
Example Output

5  
Hint

大言不惭的说说水题。。虽然做的过程并不一帆风顺

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node
    {
        char data;
        struct node *l,*r;
    }node;
    
    node *create(int len,char *pre,char *in)//老套路了，知道先序和中序搞出整棵树
    {
        int i;
        node *root;
        if(len<=0)
            return NULL;
        else{
            root = (node *)malloc(sizeof(struct node));
            char x = pre[0];
            root->data = x;
            for(i=0; i<len; i++){
                if(in[i]==x)
                    break;
            }
            root->l = create(i,pre+1,in);
            root->r = create(len-i-1,pre+i+1,in+i+1);
        }
        return root;
    }
    
    int deep(node *root)//求深度的话，就看左右子树哪个更深就返回哪个的深度，最后加个1就是整棵树的深度了
    {
        int d = 1;
        if(root){
            int dl = deep(root->l);
            int dr = deep(root->r);
            d = dl>dr?dl+1:dr+1;
        }
        else
            return 0;//一定到最后没有左右子树的话要返回0，这样就不会又加1了
        return d;
    }
    
    int main()
    {
        int len;
        char pre[100],in[100];
        while(~scanf("%d",&len)){
            scanf("%s %s",pre,in);
            node *root = create(len,pre,in);
            printf("%d\n",deep(root));
        }
        return 0;
    }