已知二叉树的前序和中序序列，构建二叉树并求后序序列，java实现。

已知二叉树的前序和中序序列，或者已知二叉树的后序和中序序列，是能够唯一确定一棵二叉树的。但是如果仅知道二叉树的前序和后序序列，一般是不能唯一确定一棵二叉树的，但是可以分析有多少种可能的二叉树，这个没有具体研究，只知道节点少的情况还能凑合分析出来，但是节点多的情况下可能性太多，很难分析。

言归正传，比如一个二叉树的前序序列是int[] pre = {1,2,4,3}，中序序列是int[] mid = {2,4,1,3}，求后序序列。（PS：这里的二叉树元素为整数，稍作改变就可以实现其他类型的元素。）

算法思想：我们知道，前序序列的第一个元素是根节点，pre[0]=1,构建这个根节点，然后往mid数组中寻找这个元素（目的是为了继续拆分中序序列），得到mid[2]=1=pre[0]。下标是2，把mid数组一分为二，左边的为pre[0]节点的左子树(2,4)，右边的为pre[0]节点的右子树(3)。

继续遍历前序序列数组，pre[1]=2，构建这个节点，然后往mid[0~1]寻找与pre[1]相等的元素，得到mid[0]=pre[1]=2，下标是0，把mid[0~1]一分为二，左边没有左子树，为空；右边右子树为（4）。左子树为空，然后拆分右子树，右子树为元素4，构建这个节点，这个节点既没有左子树也没有右子树，就开始向上构建根节点的右子树，根节点的右子树元素只有一个3，构建这个节点，这个节点既没有左子树也没有右子树，构建二叉树完毕。

说了这么多，还是来代码比较实在。

/**
 * 已知前序和中序序列，求后序序列。
 * 
 * @author mzdong
 * 
 */
public class PreMidToAfter {
	public static int index = 0; // 记录从前序序列遍历的位置

	/**
	 * 二叉树的节点的数据结构类
	 * 
	 * @author mzdong
	 * 
	 */
	private class Node {
		Node leftChild;
		Node rightChild;
		int data;

		public Node(int data) {
			leftChild = null;
			rightChild = null;
			this.data = data;
		}
	}

	/**
	 * 后序遍历
	 * 
	 * @param node
	 */
	public void afterOrder(Node node) {
		if (node != null) {
			afterOrder(node.leftChild);
			afterOrder(node.rightChild);
			System.out.print(node.data + " ");
		}
	}

	/**
	 * 已知前序和中序序列，求后序序列。
	 * 
	 * @param pre
	 * @param mid
	 * @param midStart
	 * @param midEnd
	 * @return 最终返回根节点
	 */
	public Node process(int[] pre, int[] mid, int midStart, int midEnd) {
		int mstart = midStart;
		int mend = midEnd;
		int flag = 0;
		if (index >= pre.length) {
			return null;
		}
		Node node = new Node(pre[index]);
		for (int i = mstart; i <= mend; i++) {//遍历
			if (mid[i] == pre[index]) {
				flag = i;
			}
		}
		index++;
		if (midStart < flag)
			node.leftChild = process(pre, mid, midStart, flag - 1);//是不是有点像快速排序呢。。。
		if (flag < midEnd)
			node.rightChild = process(pre, mid, flag + 1, midEnd);
		return node;
	}

	public static void main(String[] args) {
//		int[] pre = { 1, 5, 6, 10, 7, 2, 9, 3, 4, 8 };// 前序
//		int[] mid = { 6, 10, 5, 7, 1, 9, 2, 4, 3, 8 };// 中序
//		int[] after = { 10, 6, 7, 5, 9, 4, 8, 3, 2, 1 };// 后序
		 int[] pre = {1,2,4,3};//前序
		 int[] mid = {2,4,1,3};//中序
		 int[] after = {4,2,3,1};//后序
		PreMidToAfter pmta = new PreMidToAfter();
		Node root = pmta.process(pre, mid, 0, mid.length - 1);
		pmta.afterOrder(root);

	}
}
           

测试了若干个，表示结果没有问题，算法思想有点类似快速排序。

附加：若已知后序和中序序列，构建二叉树并求前序序列。由于后序序列的最后一个元素是根节点，所以要从后往前遍历，并且在构建左子树和右子树的时候，要先建右子树，再建左子树，顺序不能错。代码稍作修改即可实现，这里不再赘述。