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

代码语言：javascript复制

#include <bits/stdc  .h>
using namespace std;
struct node
{
    char data;
    struct node *lc, *rc;
};
char a[100],b[100];
int n;
struct node *creat(int len, char a[], char b[])
{
    if(len == 0) return NULL;
    int i;
    struct node *root;
    root = new node;
    root -> data = a[0];
    for(i = 0; i < len; i   )
    {
        if(a[0] == b[i])
        {
            break;
        }
    }
    root -> lc = creat(i, a   1, b);
    root -> rc = creat(len - i - 1,a   i   1, b   i   1);
    return root;
};
int fin(struct node *root)
{
   // cout << "yes" << endl;
    int d1, d2;
    int h = 0;
    if(root)
    {
        d1 = fin(root -> lc);
        d2 = fin(root -> rc);
        h = max(d1 1,d2  1);
    }
    return h;
}
int main()
{
        while(~scanf("%d",&n))
        {
        scanf("%s %s", a,b);
        struct node *root;
        root = creat(n,a,b);
        int ans = fin(root);
        printf("%dn",ans);
    }

    return 0;
}

二叉树

0 人点赞