二叉树 根据前序遍历 中序遍历 写出后序遍历

思路

前序遍历：中——左——右

中序遍历：左——中——右

先确定前序遍历的第一个节点为根节点，然后在中序遍历中找到该根节点，以根节点为基点，前一部分为左子树，后一部分为右子树。然后按照递归分部分操作。

伪代码

二叉树前序中序后序图，主方法{

根节点 = 创建树（0，节点个数-1,0，结点个数-1，前序节点数组，中序节点数组）；

后续遍历打印节点

}

创建树（前序左，前序右，中序左，中序右，前序节点数组，中序节点数组）{

if(前序左>前序右)返回空

新建根节点root = 前序节点数组[前序左]；

中序数组索引 k = 0；

遍历找到在 中序节点数组中的根节点 的索引    并赋值为给 k ;

左子树结点个数 num = k - 中序左；

root.左子树 = 创建树（前序左+1，前序左+num，中序左，k - 1，前序节点数组，中序节点数组）；

root.右子树 = 创建树（前序左+1+num，前序右，k + 1，中序右 ，前序节点数组，中序节点数组）；

返回根root；

}

二叉树前序中序后续怎么看、 

打印节点（根节点root，结点个数）{

if( root 为空 ) return;

 打印节点（根节点root.左子树，结点个数）；

 打印节点（根节点root.右子树，结点个数）；

输出root的值

}

代码

public static void main(String[] args) {int [] pre = new int[] {4,2,1,3,5,7,6};int [] in = new int [] {1,2,3,4,5,6,7};int nodeNum = 7;TreeNode root = creat(0,nodeNum-1,0,nodeNum-1,pre,in);//创建树printPost(root,nodeNum);//打印节点}static int num = 0;private static void printPost(TreeNode root,int nodeNum) {//后续遍历 打印节点if(root==null)return;printPost(root.left,nodeNum);printPost(root.right,nodeNum);System.out.print(root.val);num++;if(num<nodeNum)System.out.print(" ");}private static TreeNode creat(int prel, int prer, int inl, int inr,int[]pre,int []in) {if(prel>prer) return null;TreeNode root = new TreeNode(pre[prel]);//创建根节点int k = 0;								//根节点在中序数组中的索引for (k = inl; k < in.length; k++) {		//找到找到索引if(pre[prel]==in[k]) {break;}}int numleft = k - inl;					//左子树节点个数//参数依次为 (在前序数组中 左子树起始位置，在前序数组中 左子树终止位置，//            在中序数组中 左子树起始位置，在前序数组中 左子树终止位置，//				前序数组，中序数组)root.left = creat(prel+1, prel+numleft, inl, k-1, pre, in);//参数依次为 (在前序数组中 右子树起始位置，在前序数组中 右子树终止位置，//            在中序数组中 右子树起始位置，在前序数组中 右子树终止位置，//				前序数组，中序数组)root.right = creat(prel+numleft+1, prer, k+1, inr, pre, in);return root;}

中序遍历二叉排序树所得到的序列是、