建树与递归

Construct Binary Tree from Inorder and Anotherorder Traversal

tree *post(int root, int start, int end) {
    if (start > end)return nullptr;
    int i = start;
    while (i < end && inorder[i] != preorder[root]) i++;
    tree *t = new tree;
    t->left = post(root + 1, start, i - 1);
    t->right = post(root + i - start + 1, i + 1, end);
    t->w = preorder[root];
    if (root < n)print(t->w);
    return t;
}

Return Level Traversal from Inorder and Anotherorder Traversal

vector<int> level(MAXN, -1);

tree *post(int root, int start, int end, int index) {
    if (start > end)return nullptr;
    int i = start;
    while (i < end && inorder[i] != preorder[root]) i++;
    tree *t = new tree;
    t->left = post(root + 1, start, i - 1, index * 2 + 1);
    t->right = post(root + i - start + 1, i + 1, end, index * 2 + 2);
    t->w = preorder[root];
    if (root < n)level[index] = t->w;
    return t;
}