??今天在lintCode上面做了一道題，關于二叉樹的構造，是一道數據結構中常見的問題。
1. 概覽
(1).題意
根據中序遍歷和后序遍歷樹構造二叉樹
注意事項
你可以假設樹中不存在相同數值的節(jié)點
(2).樣例
給出中序遍歷：[1,2,3]和前序遍歷：[2,1,3]. 返回如下的樹:
2
/ \
1 3
2.解題思路
??這道題是一道典型的數據結構的問題。在數據結構中，我們知道有三種遍歷：先序遍歷，中序遍歷和后序遍歷。在這三種遍歷中，如果想要任取兩種遍歷來構造二叉樹的話，必須含有中序遍歷，也就是說，只有先序遍歷和中序遍歷，后序遍歷和中序遍歷這兩種組合才能成功的構造二叉樹。
??我們知道必須含有中序遍歷才能成功的構造二叉樹，那為什么呢？
??要搞清楚這個原因，我們必須清楚二叉樹的三種遍歷的特性。中序遍歷是先遍歷左節(jié)點，再遍歷根，最后遍歷右節(jié)點。我們可以利用這個特性，來分清哪些是根節(jié)點的左子樹，哪些是根節(jié)點的右子樹。
??例如：以下一棵樹
??我們能得到中序遍歷序列：[3,2,4,1,6,5,7]。如果我們得到一個根節(jié)點，那么這個根節(jié)點的左邊肯定是根節(jié)點的左子樹，右邊肯定是根節(jié)點的右子樹。那么我們怎么能拿到這個根節(jié)點呢？
??該題是中序遍歷和后序遍歷的問題，我們可以通過后序遍歷的序列來獲得。就拿上面的樹來舉例子，后序遍歷的序列是：[3,4,2,6,7,5,1]。而后序遍歷的特性，先遍歷子樹(先左或者先右沒有特定的規(guī)則，通常來說，是先左再右)，最后再遍歷根，也就是說，根是最后遍歷的。那在后序遍歷的序列中，最后出現(xiàn)的肯定是根節(jié)點。
??例如：拿上面的樹來說，中序遍歷的序列是：[3,2,4,1,6,5,7]，后序遍歷的序列是：[3,4,2,6,7,5,1]。在后序遍歷的序列最后出現(xiàn)的是1，那么1肯定是整個樹的根節(jié)點，同時在中序遍歷中，我們將序列分為三個中部分：[1]是根節(jié)點（根據后序遍歷得到的），[3,2,4]是1的左子樹，[6,5,7]是1的右子樹。同時遞歸遍歷[3,2,4]序列，[6,5,7]序列。這兩個序列中同時根據后序遍歷來找到根節(jié)點，在中序遍歷中根節(jié)點的左邊的序列就是根節(jié)點的左子樹，右邊的序列就是根節(jié)點的右子樹。
??知道這些原理，寫代碼相對來說，就簡單的很多。
3.代碼
private int index = 0;
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder.length == 0 || postorder.length == 0) {
return null;
}
index = postorder.length - 1;
return createBST(inorder, postorder, 0, postorder.length - 1);
}
private TreeNode createBST(int[] inorder, int [] postorder,int start, int end) {
//找到在后序遍歷序列中找到根節(jié)點
int val = postorder[index];
int i = 0;
for(i = 0; i < end; i++) {
//在中序遍歷中，找到根節(jié)點的位置
if(inorder[i] == val) {
break;
}
}
//構造根節(jié)點
TreeNode node = new TreeNode(val);
//如果end大于等于i + 1,表示還有右子樹
if(end >= i + 1) {
//在后序遍歷中，根節(jié)點的左移
--index;
node.right = createBST(inorder, postorder, i + 1, end);
}
//如果start 小于等于 i- 1,表示還有左子樹
if(start <= i - 1) {
--index;
node.left = createBST(inorder, postorder, start, i - 1);
}
return node;
}
