给定二叉树的前序遍历和中序遍历，，输出后序遍历结果。
代码：
#include <iostream>#include <vector>using namespace std;struct TreeNode{int val;TreeNode *left;TreeNode *right;TreeNode (int x) : val(x), left(NULL),right(NULL){}};TreeNode * reConstructBinaryTree (vector<int> pre ,vector<int> in){if( pre.size()==NULL|| in.size()==NULL)return NULL;TreeNode *root = new TreeNode(pre[0]); //前序遍历：根左右，，第一个为根int i;for ( i =0; i<in.size()&& in[i]!=pre[0]; i++); //找到中序遍历中根结点的位置i.vector<int> pre_left, in_left, pre_right, in_right;int pre_i=1;for(int j=0; j<in.size();j++){if(j<i){in_left.push_back(in[j]);pre_left.push_back(pre[pre_i]);pre_i++;}else if(j>i){in_right.push_back(in[j]);pre_right.push_back(pre[pre_i]);pre_i++;}}root->left = reConstructBinaryTree(pre_left, in_left);root->right = reConstructBinaryTree(pre_right, in_right);return root;}void Print(vector<int> &vec){int num=vec.size();if(vec.size()==0)return;else{for(int i=0; i<vec.size(); i++){cout<<vec[i]<<" ";}cout<<endl;}}void PostOrder(TreeNode* root) //后续遍历{if(root==NULL)return ;else{PostOrder(root->left);PostOrder(root->right);cout<<root->val<<" ";}return;}int main(){vector<int> pre={ 1,2,4,7,3,5,6,8};vector<int> in = {4,7,2,1,5,3,8,6 };cout<<"前序遍历为："<<endl;Print(pre);cout<<"中序遍历为："<<endl;Print( in);TreeNode* root = reConstructBinaryTree( pre, in);cout<<"后序遍历为："<<endl;PostOrder(root);return 0;}
运行结果：
前序遍历为：1 2 4 7 3 5 6 8中序遍历为：4 7 2 1 5 3 8 6后序遍历为：7 4 2 5 8 6 3 1Process returned 0 (0x0) execution time : 0.161 sPress any key to continue.
如果觉得《《剑指offer》面试题6——重构二叉树——已知 前序遍历和中序遍历 求后序遍历（C++）》对你有帮助，请点赞、收藏，并留下你的观点哦！
