📚PTA习题解析💡 根据后序和中序遍历输出先序遍历（C++实现）🎉

在数据结构的学习过程中，树的遍历是一个重要知识点。今天，我们来挑战一个有趣的题目：如何通过后序遍历和中序遍历来还原先序遍历？🤔 这个问题不仅考验你的逻辑推理能力，还锻炼了代码实现技巧。

首先，我们需要理解三种遍历方式的区别：

- 后序遍历：左子树 → 右子树 → 根节点

- 中序遍历：左子树 → 根节点 → 右子树

- 先序遍历：根节点 → 左子树 → 右子树

题目要求是利用后序和中序序列重建先序序列。核心思路是从后序序列中找到根节点，然后在中序序列中划分左右子树，递归处理即可。💪

以下是C++代码实现的框架：

```cpp

void buildPreOrder(const vector& inorder, const vector& postorder) {

if (inorder.empty() || postorder.empty()) return;

int rootVal = postorder.back(); // 找到根节点值

cout << rootVal << " "; // 输出根节点

// 在中序序列中找到根节点位置

size_t rootIndex = find(inorder.begin(), inorder.end(), rootVal) - inorder.begin();

// 递归处理左右子树

buildPreOrder(vector(inorder.begin(), inorder.begin() + rootIndex),

vector(postorder.begin(), postorder.begin() + rootIndex));

buildPreOrder(vector(inorder.begin() + rootIndex + 1, inorder.end()),

vector(postorder.begin() + rootIndex, postorder.end() - 1));

}

```

通过这段代码，我们可以高效地完成任务！🌟 实践中建议多加调试，确保每一步都清晰准确。💪 欢迎大家尝试练习，一起进步吧！🚀