二叉树问题

朴灿烈づ我的快乐病毒、 2022-01-07 14:39 220阅读 0赞

### 题目描述 ###

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

### 输入 ###

输入包含多组测试数据，每组输入首先给出正整数N（<=50），为树中结点总数。下面2行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。

### 输出 ###

对于每组输入，输出一个整数，即该二叉树的高度。

### 样例输入 ###

> 9  
> ABDFGHIEC  
> FDHGIBEAC  
> 7  
> Abcdefg  
> gfedcbA

### 样例输出 ###

> 5  
> 7

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<map>
    #define ll long long
    using namespace std;
    map<char,int>q;
    int n,h[1024],ans;
    string s1,s2;
    int lson[1024],rson[1024];
    int tag[1024];
    char buildtree(int s,int t){
        memset(tag,0,sizeof(tag));
        if(s==t) return s2[s];
        for(int i=s;i<=t;i++){
            tag[s2[i]]=1;
            //cout<<s2[i];
        }
        //cout<<endl;
        int lx=-1,rx=-1;
        for(int i=0;i<n;i++){
            if(lx==-1){
                if(tag[s1[i]]){
                    lx=i;
                }
            }
            else{
                if(!tag[s1[i]]){
                    rx=i-1;
                    break;
                }
            }
        }
        if(rx==-1) rx=t;
        char root=s1[lx];int pla;
        for(int i=s;i<=t;i++){
            if(root==s2[i]){
                pla=i;
                break;
            }
        }
        if(s<=pla-1) lson[root]=buildtree(s,pla-1);
        if(pla+1<=t) rson[root]=buildtree(pla+1,t);
        return root;
    }
    void dfs(char ss){
        if(ss==0){
            return;
        }
        ans=max(ans,h[ss]);
        h[lson[ss]]=h[rson[ss]]=h[ss]+1;
        dfs(lson[ss]);
        dfs(rson[ss]);//cout<<ss<<'*';
    }
    int main(){
        while(cin>>n){
            memset(h,0,sizeof(h));
            memset(lson,0,sizeof(lson));
            memset(rson,0,sizeof(rson));
            ans=0;
            //q.erase(q.begin(),q.end());
            cin>>s1>>s2;
            char x=buildtree(0,n-1);
            h[x]=1;
            dfs(x);
            cout<<ans<<endl;
        }
        return 0;
    }

转载于:https://www.cnblogs.com/sz-wcc/p/11071879.html