分析

参考之前的题解：中序遍历+前序遍历构建二叉树

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n,idx;
char pre[55],ino[55];
unordered_map<char,int> mp;     //哈希表记录中序遍历中每个点的位置
struct node{
    char c;
    node *left;
    node *right;
    node(char x): c(x),left(NULL),right(NULL) {}
};
node* dfs(int l,int r)
{
    if(l>r) return NULL;
    int pos=mp[pre[idx]];
    auto t=new node(pre[idx++]);
    t->left=dfs(l,pos-1);
    t->right=dfs(pos+1,r);
    return t;
}
int main()
{
    cin>>n;
    cin>>pre+1;
    cin>>ino+1;
    for(int i=1;i<=n;i++)
         mp[ino[i]]=i;
    idx=1;
    auto root=dfs(1,n); //递归建树

    queue<node*> q;   //bfs求二叉树深度
    q.push(root);
    int ans=0;
    while(q.size())
    {
        ans++;
        int len=q.size();
        for(int i=0;i<len;i++)
        {
            auto t=q.front();
            q.pop();
            if(t->left) q.push(t->left);
            if(t->right) q.push(t->right);
        }
    }
    cout<<ans;
    return 0;
}