【数据结构与算法】根据 前序遍历序列和中序遍历序列 还原二叉树

《数据结构实验指导 - C++语言版》题目集 练习5-3 还原二叉树

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

输入格式:

输入首先给出正整数 n（≤50），为树中结点总数。随后 2 行先后给出前序和中序遍历序列，均是长度为 n 的不包含重复英文字母（区别大小写）的字符串。

输出格式:

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

输入样例:

9
ABDFGHIEC
FDHGIBEAC

输出样例:

5

#include <bits/stdc++.h>
using namespace std;
int n;
string pre,mid;

struct Node {
    char val;
    Node* left;
    Node* right;
    Node(char x):val(x),left(nullptr),right(nullptr) {}
};

Node* buildTree(int pre_s, int pre_e, int mid_s, int mid_e) {
    if (pre_s>pre_e||mid_s>mid_e) return nullptr;
    char root = pre[pre_s];
    int root_idx_in_mid = 0;
    while (mid[root_idx_in_mid]!=root) {
        root_idx_in_mid++;
    }
    int left_nodes_len = root_idx_in_mid - mid_s; 
    Node* node = new Node(root);
    node->left = buildTree(pre_s+1,pre_s+left_nodes_len,mid_s,root_idx_in_mid-1);
    node->right = buildTree(pre_s+1+left_nodes_len,pre_e,root_idx_in_mid+1,mid_e);
    return node;
}

int getHeight(Node* root) {
    if (root == nullptr) return 0;
    return max(getHeight(root->left), getHeight(root->right)) + 1;
}

int main() {
    cin>>n;
    cin>>pre>>mid;
    Node* root = buildTree(0,n-1,0,n-1);
    cout<<getHeight(root)<<endl;
    return 0;
}