例子：
前序：1, 2, 3, 4, 5, 6（根左右） 中序：3, 2, 4, 1, 6, 5（左根右） 后序：3, 4, 2, 6, 5, 1（左右根） 1、先说根据前序中序求后序，前序总是沿着根往树的左边一直跑，所以前序遍历的前面肯定是根节点 中序则是按照：左—–根—–右 的顺序排列，其中左，右子树按照同样的结构，所以我们可以从前序遍历的根节点入手，迅速定位中序序列的结构中左子树和右子树部分，而后序遍历无非就是：左子树，右子树，访问根。 代码如下， root是前序列表中代表根节点的点的下标 start，end是中序遍历中当前处理的树的开始与结尾 #include<iostream> using namespace std; int pre[] = {1, 2, 3, 4, 5, 6}; int mid[] = {3, 2, 4, 1, 6, 5}; void post(int root, int start, int end) { if(start > end) return ; int i = start; while(i < end && mid[i] != pre[root]) i++; //定位根在中序的位置 post(root + 1, start, i - 1); //递归处理左子树 post(root + 1 + i - start, i + 1, end); //递归处理右子树 //cout<<pre[root]; //访问当前树的根 cout<<mid[i]; } int main() { post(0, 0, 5); return 0; }2、再说根据后序中序输出前序，中序已经说过了，中序是按照：左—–根—–右 的顺序排列，其中左，右子树按照同样的结构，后序则是按照：左——右——根的顺序，其中左，右 按照同样的结构，后序遍历的最后肯定是根节点，所以我们可以从后序序列的根节点入手，把中序给分割出左 右 根的部分，然后就可以得到前序遍历啦！ 同样代码如下： root是后序列表中代表根节点的点的下标 start，end是中序遍历中当前处理的树的开始与结尾
#include<iostream> using namespace std; int post[] = {3, 4, 2, 6, 5, 1}; int mid[] = {3, 2, 4, 1, 6, 5}; void pre(int root, int start, int end) { if(start > end) return ; int i = start; while(i < end && mid[i] != post[root]) i++; //定位根在中序的位置 cout<<mid[i]; //访问当前处理的树的根 pre(root-1-(end-i), start, i - 1); //递归处理左子树 pre(root-1, i + 1, end); //递归处理右子树 } int main() { pre(5, 0, 5); return 0; }注意每一次递归时，准确的定位根节点所在的位置很重要。
