【数据结构与算法】根据后序和中序遍历输出前序遍历

《数据结构实验指导 - C++语言版》题目集 实验5-4 根据后序和中序遍历输出前序遍历

本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的前序遍历结果。

输入格式:

第一行给出正整数 n (≤30)，是树中结点的个数。随后两行，每行给出 n 个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。

输出格式:

在一行中输出Preorder: 以及该树的前序遍历结果。数字间有1个空格，行末不得有多余空格。

输入样例:

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例:

Preorder: 4 1 3 2 6 5 7

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

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

vector<int> post_v;
vector<int> in_v;

Node* buildTree(int post_s, int post_e, int in_s, int in_e) {
    if (post_s > post_e || in_s > in_e) return nullptr;
    Node* root = new Node(post_v[post_e]);
    int idx = in_s;
    while (idx < in_e && root->val != in_v[idx]) {
        idx++;
    }
    int left_len = idx - in_s;
    root->left = buildTree(post_s, post_s + left_len - 1, in_s, idx - 1); // 注意是post_s+left_len-1而不是post_s+left_len，根据后序遍历和中序遍历左右节点数相等
    root->right = buildTree(post_s + left_len, post_e - 1, idx + 1, in_e);
    return root;
}

void dfs(Node* root) {
    if (root == nullptr) return;
    cout << " " << root->val;
    dfs(root->left);
    dfs(root->right);
}

int main() {
    cin >> n;
    post_v.resize(n);
    in_v.resize(n);
    for (int i = 0;i < n;i++) cin >> post_v[i];
    for (int i = 0;i < n;i++) cin >> in_v[i];
    Node* root = buildTree(0, n - 1, 0, n - 1);
    cout << "Preorder:";
    dfs(root);
    return 0;
}