题解：#8912 - 帖子

1. 题目描述

给定一个二叉树的 中序遍历 和 后序遍历 序列，要求构建出该二叉树，并输出其 前序遍历 结果。

2. 解决思路

观察性质
- 后序遍历 的最后一个节点是当前子树的 根节点。
- 中序遍历 中，根节点左侧的部分是左子树，右侧的部分是右子树。
递归构建二叉树
- 找到 后序遍历的最后一个元素，设为根节点。
- 在 中序遍历 中找到该节点的位置，确定 左子树和右子树的范围。
- 递归构建 左子树和右子树。
- 通过数组 treeArray 记录所有节点的信息。
前序遍历输出
- 递归遍历树，先访问根节点，再访问左子树，最后访问右子树。

3. 复杂度分析

**建立 inorderIndex **：
构建二叉树：
前序遍历：
总时间复杂度：

4. 示例

输入

9 3 15 20 7 9 15 7 20 3

其中：

前 n=5 个数是 中序遍历 [9, 3, 15, 20, 7]
后 n=5 个数是 后序遍历 [9, 15, 7, 20, 3]

构造的二叉树

前序遍历输出

3 9 20 15 7

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

// 定义树的节点结构体
struct TreeNode {
    int val;    // 节点值
    int left;   // 左子树索引
    int right;  // 右子树索引
};

vector<int> inorder, postorder;
unordered_map<int, int> inorderIndex;
vector<TreeNode> treeArray;

/**
 * 递归构建二叉树
 * @param inorderStart  中序遍历起始索引
 * @param inorderEnd    中序遍历终止索引
 * @param postorderStart 后序遍历起始索引
 * @param postorderEnd   后序遍历终止索引
 * @return 根节点在 treeArray 中的索引
 */
int buildTree(int inorderStart, int inorderEnd, int postorderStart, int postorderEnd) {
    if (inorderStart > inorderEnd || postorderStart > postorderEnd) {
        return -1;  // 返回-1表示当前没有子树
    }

    // 后序遍历的最后一个元素是根节点
    int rootVal = postorder[postorderEnd];

    // 创建树节点，并存储在数组中
    TreeNode newNode;
    newNode.val = rootVal;
    newNode.left = -1;
    newNode.right = -1;
    int rootIndex = treeArray.size();
    treeArray.push_back(newNode);

    // 在中序遍历中找到根节点的位置
    int rootIndexInInorder = inorderIndex[rootVal];
    int leftSubtreeSize = rootIndexInInorder - inorderStart;

    // 递归构建右子树和左子树
    int rightSubtreeIndex = buildTree(rootIndexInInorder + 1, inorderEnd, postorderStart + leftSubtreeSize, postorderEnd - 1);
    int leftSubtreeIndex = buildTree(inorderStart, rootIndexInInorder - 1, postorderStart, postorderStart + leftSubtreeSize - 1);

    // 设置当前节点的左右子树
    treeArray[rootIndex].left = leftSubtreeIndex;
    treeArray[rootIndex].right = rightSubtreeIndex;

    return rootIndex;  // 返回当前树节点在数组中的索引
}

/**
 * 前序遍历二叉树
 * @param rootIndex 当前遍历的根节点索引
 * @param result    存储前序遍历结果
 */
void preorderTraversal(int rootIndex, vector<int>& result) {
    if (rootIndex == -1) {
        return;
    }

    // 添加当前节点的值
    result.push_back(treeArray[rootIndex].val);

    // 递归遍历左子树和右子树
    preorderTraversal(treeArray[rootIndex].left, result);
    preorderTraversal(treeArray[rootIndex].right, result);
}

int main() {
    // 读取输入
    int num;
    vector<int> input;
    
    while (cin >> num) {
        input.push_back(num);
    }
    
    int n = input.size() / 2;
    inorder.assign(input.begin(), input.begin() + n);
    postorder.assign(input.begin() + n, input.end());

    // 记录中序遍历中每个值的位置
    for (int i = 0; i < n; i++) {
        inorderIndex[inorder[i]] = i;
    }

    // 重建二叉树并得到根节点索引
    int rootIndex = buildTree(0, n - 1, 0, n - 1);

    // 获取前序遍历结果
    vector<int> result;
    preorderTraversal(rootIndex, result);

    // 输出前序遍历结果
    for (size_t i = 0; i < result.size(); ++i) {
        cout << result[i] << (i == result.size() - 1 ? "" : " ");
    }

    return 0;
}

题解：#8912 审核通过

1. 题目描述

2. 解决思路

3. 复杂度分析

4. 示例

输入

构造的二叉树

前序遍历输出