已知二叉樹的前序和中序序列，建構二叉樹并求後序序列，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);

	}
}
           

測試了若幹個，表示結果沒有問題，算法思想有點類似快速排序。

附加：若已知後序和中序序列，建構二叉樹并求前序序列。由于後序序列的最後一個元素是根節點，是以要從後往前周遊，并且在建構左子樹和右子樹的時候，要先建右子樹，再建左子樹，順序不能錯。代碼稍作修改即可實作，這裡不再贅述。