题解思路

要根据二叉树的中序遍历和后序遍历序列重建二叉树，并输出其先序遍历序列。关键点在于：

1. 后序遍历的最后一个元素是根节点。
2. 在中序遍历中找到根节点，根节点左侧是左子树的中序遍历序列，右侧是右子树的中序遍历序列。
3. 根据左子树的节点数量，将后序遍历序列（除最后一个根节点外）分割为左子树的后序遍历序列和右子树的后序遍历序列。
4. 递归处理左右子树，先序遍历的顺序为：根节点 -> 左子树先序遍历 -> 右子树先序遍历。

递归函数设计：

• 根节点：后序遍历的最后一个字符。
• 分割中序序列：找到根节点在中序序列中的位置 index，左侧 [0, index-1] 为左子树中序序列，右侧 [index+1, end] 为右子树中序序列。
• 分割后序序列：左子树后序序列长度为 left_size = index，从后序序列开头取 left_size 个字符；右子树后序序列长度为 right_size = n - index - 1，从 left_size 位置开始取 right_size 个字符。
• 递归构建：对左右子树递归调用，得到左子树先序序列 left_pre 和右子树先序序列 right_pre。
• 合并结果：根节点 + left_pre + right_pre。

代码实现

#include <iostream>
#include <string>
using namespace std;

string build(string in, string post) {
    if (in.empty()) {
        return "";
    }
    int n = in.size();
    char root = post[n - 1]; // 后序遍历的最后一个字符是根节点
    size_t pos = in.find(root); // 在中序遍历中查找根节点位置
    if (pos == string::npos) {
        return ""; // 未找到根节点（题目保证不会发生，但为健壮性处理）
    }
    int index = static_cast<int>(pos);
    int left_size = index; // 左子树节点数
    int right_size = n - index - 1; // 右子树节点数

    // 分割中序遍历序列：左子树和右子树
    string in_left = in.substr(0, left_size);
    string in_right = in.substr(index + 1, right_size);

    // 分割后序遍历序列：左子树和右子树（排除最后一个根节点）
    string post_left = post.substr(0, left_size);
    string post_right = post.substr(left_size, right_size);

    // 递归构建左右子树
    string left_pre = build(in_left, post_left);
    string right_pre = build(in_right, post_right);

    // 先序遍历：根 + 左子树先序 + 右子树先序
    return string(1, root) + left_pre + right_pre;
}

int main() {
    string in_order, post_order;
    getline(cin, in_order); // 读取中序遍历序列
    getline(cin, post_order); // 读取后序遍历序列

    string pre_order = build(in_order, post_order);
    cout << pre_order << endl;
    return 0;
}

递归函数 build：

• 处理空子树情况，直接返回空字符串。
• 通过后序遍历的最后一个字符确定根节点。
• 在中序遍历中查找根节点位置，分割左右子树。
• 根据左右子树的节点数量，分割后序遍历序列。
• 递归构建左右子树的先序遍历序列。
• 合并结果：根节点 + 左子树先序 + 右子树先序。

复杂度分析

• 时间复杂度：每次递归需要在中序序列中查找根节点，最坏情况为 ，其中 为节点数（，实际效率足够）。
• 空间复杂度：递归栈深度 ，每次递归产生子串，总空间 （ 很小，可忽略）。 当然可以。以下是以标准算法题解风格（如 LeetCode / 牛客风格）对「二叉树的前序、中序、后序遍历」的完整题解，兼顾定义清晰、逻辑严密、边界处理、时空分析、代码实现（C++），并保留你偏好的风格：逻辑正确性优先、结构紧凑、命名规范、可直接验证执行。

总结拓展

三种遍历的递归结构完全一致，唯一差异是：

注意：每进入一个节点，都先处理其左子树直至叶节点（深度优先），回溯时再处理右子树——这是 DFS 的本质。

代码实现

#include <vector>
using namespace std;

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

class Solution {
public:
    // 前序遍历：根 → 左 → 右
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        preorderHelper(root, res);
        return res;
    }

    // 中序遍历：左 → 根 → 右
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorderHelper(root, res);
        return res;
    }

    // 后序遍历：左 → 右 → 根
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        postorderHelper(root, res);
        return res;
    }

private:
    void preorderHelper(TreeNode* node, vector<int>& res) {
        if (node == nullptr) return;  // 边界：空节点直接返回
        res.push_back(node->val);      // 1. 访问根
        preorderHelper(node->left, res);   // 2. 递归左子树
        preorderHelper(node->right, res);  // 3. 递归右子树
    }

    void inorderHelper(TreeNode* node, vector<int>& res) {
        if (node == nullptr) return;
        inorderHelper(node->left, res);    // 1. 递归左子树
        res.push_back(node->val);          // 2. 访问根
        inorderHelper(node->right, res);   // 3. 递归右子树
    }

    void postorderHelper(TreeNode* node, vector<int>& res) {
        if (node == nullptr) return;
        postorderHelper(node->left, res);   // 1. 递归左子树
        postorderHelper(node->right, res);  // 2. 递归右子树
        res.push_back(node->val);           // 3. 访问根
    }
};

复杂度分析