已知前序中序输出后序(java)

例子：

前序：1, 2, 3, 4, 5, 6（根左右）
中序：3, 2, 4, 1, 6, 5（左根右）
后序：3, 4, 2, 6, 5, 1（左右根）
1、先说根据前序中序求后序，前序总是沿着根往树的左边一直跑，所以前序遍历的前面肯定是根节点
中序则是按照：左—–根—–右 的顺序排列，其中左，右子树按照同样的结构，所以我们可以从前序遍历的根节点入手，迅速定位中序序列的结构中左子树和右子树部分，而后序遍历无非就是：左子树，右子树，访问根。
代码如下，
root是前序列表中代表根节点的点的下标
start，end是中序遍历中当前处理的树的开始与结尾

public class 已知前序中序输出后序 {
public    static   int pre []=new int[]{1, 2, 3, 4, 5, 6};
public    static   int mid[]=new int[]{3, 2, 4, 1, 6, 5};
    public static   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);
        System.out.print(mid[i] + " ");
    }

    public static void main(String[] args) {
                post(0,0,pre.length-1);

    }
}

再说根据后序中序输出前序，中序已经说过了，中序是按照：左—–根—–右 的顺序排列，其中左，右子树按照同样的结构，后序则是按照：左——右——根的顺序，其中左，右 按照同样的结构，后序遍历的最后肯定是根节点，所以我们可以从后序序列的根节点入手，把中序给分割出左 右 根的部分，然后就可以得到前序遍历啦！
同样代码如下：
root是后序列表中代表根节点的点的下标
start，end是中序遍历中当前处理的树的开始与结尾

public class  Main {
public    static   int mid[]=new int[]{3, 2, 4, 1, 6, 5};
public    static   int post[]=new int[]{3, 4, 2, 6, 5, 1};

    public static   void pre(int root, int start, int end){
        if(start>end)
            return;
        int i = start;
        //定位根在中序的位置
        while(i < end && mid[i] != post[root]) i++;
        //访问当前处理的树的根
        System.out.println(mid[i]);
        pre(root-1-(end-i), start, i - 1);  //递归处理左子树
        pre(root-1, i + 1, end);  //递归处理右子树

    }
 public static void main(String[] args) {
              pre(post.length-1,0, post.length-1);
    }
}