数据结构实验之二叉树四：（先序中序）还原二叉树

灰太狼 2022-06-04 23:23 130阅读 0赞

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

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

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

Output

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

9  
ABDFGHIEC  
FDHGIBEAC  
Example Output

5  
Hint

Author

xam

#include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    
    
    const int MAX = 55;
    
    typedef struct node
    {
        char data;
        struct node *cl, *cr;
    } tree, *ptree;
    
    
    
    ptree get_pretree(int n, char pre[], char mid[])
    {
        if (n == 0)
            return NULL;
        char *p;
        for (p = mid; p != '\0'; p++)
        {
            if (*p == pre[0])
                break;
        }
        int len = p - mid;
        ptree root = new tree;
        root->data = pre[0];
        root->cl = get_pretree(len, pre + 1, mid);
        root->cr = get_pretree(n - len - 1, pre + len + 1, p + 1);
        return root;
    }
    
    int get_deep(ptree root)
    {
        if (root == NULL)
            return 0;
        int dp = 0;
        int dl = get_deep(root->cl);
        int dr = get_deep(root->cr);
        dp = dl > dr ? dl + 1 : dr + 1;
        return dp;
    }
    
    
    int main()
    {
        char pre[MAX], mid[MAX];
        int n;
        while (cin >> n)
        {
            cin >> pre >> mid;
            ptree root = NULL;
            root = get_pretree(n, pre, mid);
            int ct = get_deep(root);
            cout << ct << endl;
        }
        return 0;
    }