先中二叉建树

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    char val;
    TreeNode* l;
    TreeNode* r;
};

// TODO(递归到当前这一层， mid 为 当前构建这颗树中序节点 ，hou 当前的后序遍历节点)
// TODO len 当前构建这颗树的节点个数
int ans = 0;
TreeNode* build(char xian[], char mid[], int len, int high) {
    if (len == 0) return NULL;
    ans = max(ans, high);
    char tmp = xian[0];
    int index = -1;
    for(int i = 0; i < len; i++) {
        if (tmp == mid[i]) {
            index = i ;
            break;
        }
    }
    TreeNode* root = new TreeNode();
    root->val = tmp;
    // todo 建左子树
    // todo 1. xian + 1 ~ xian + index 先序范围
    // todo 2. mid + 0 ~ mid + index - 1
    root->l = build(xian + 1, mid, index, high + 1);
    // todo 建右子树
    // todo 1. xian + index + 1 ~  xian + index + 1 + (len - index - 1) - 1 线序中右子树的范围
    // todo 2. mid + index + 1 ~
    root->r = build(xian + index + 1, mid + index + 1, len - index - 1, high + 1);
    return root;
}

char a[55], b[55];
int main() {
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> b[i];

    TreeNode* root = build(a, b, n, 1);
    cout << ans << endl;
    return 0;
}