本文章讲解如何通过给定的前序和中序遍历序列重建二叉树，并进一步计算其后序遍历结果，适合编程与算法学习者。
根据给定的前序遍历和中序遍历结果求解二叉树的后序遍历的C++代码如下：
首先定义一个结构体表示二叉树节点：
```cpp
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
};
```
接着实现根据给定前序序列和中序序列构造二叉树的方法，再通过递归方式输出后序遍历结果。
1. 创建一个辅助函数用于查找根节点在中序遍列中的位置。
2. 编写主函数构建整棵树结构：
- 根据当前的前驱索引找到根结点
- 用该值创建一个新的树结点
- 在中序序列里定位到这个新创建的节点，这样就能知道左子树和右子树在中序遍历中的范围。
- 利用这些信息递归地构建左右子树。
3. 实现后序遍历输出：
- 从根结点开始
- 先访问左孩子再访问右孩子最后打印当前节点值
完整代码实现如下：
```cpp
#include
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
};
TreeNode* buildTree(int pre[], int in[], int start, int end) {
static int idx = 0; // 前序序列的当前索引
if (start > end)
return nullptr;
TreeNode *root = new TreeNode(pre[idx]);
int pos = -1;
for (int i=start ;i<=end;i++) {
if(in[i] == pre[idx]) {
pos=i; // 查找中序序列里根节点的位置
break;
}
}
idx++;
root->left = buildTree(pre, in, start ,pos-1); // 构建左子树
root->right = buildTree(pre, in, pos+1,end ); // 构建右子树
return root;
}
void postOrder(TreeNode *root) {
if (root == nullptr)
return;
postOrder(root->left);
postOrder(root->right);
cout << root->val << ;
}
```
上述代码可以实现从给定的前序遍历和中序遍历结果构造二叉树，并输出其后序遍历的结果。
5星
