算法1

輸入：前序遍歷，中序遍歷

尋找樹的root，前序遍歷的第一節點G就是root。
觀察前序遍歷GDAFEMHZ，知道了G是root，剩下的節點必然在root的左或右子樹中的節點。
觀察中序遍歷ADEFGHMZ。其中root節點G左側的ADEF必然是root的左子樹中的節點，G右側的HMZ必然是root的右子樹中的節點，root不在中序遍歷的末尾或開始就說明根節點的兩顆子樹都不為空。
觀察左子樹ADEF，按照前序遍歷的順序來排序為DAFE，因此左子樹的根節點為D，並且A是左子樹的左子樹中的節點，EF是左子樹的右子樹中的節點。
同樣的道理，觀察右子樹節點HMZ，前序為MHZ，因此右子樹的根節點為M，左子節點H，右子節點Z。

觀察發現，上面的過程是遞歸的。先找到當前樹的根節點，然後劃分為左子樹，右子樹，然後進入左子樹重複上面的過程，然後進入右子樹重複上面的過程。最後就可以還原一棵樹了：

更多C/C++學習資料，請私信我“代碼”獲取，或群：708219153

從而得到PostOrder: AEFDHZMG

改進：

更進一步說，其實，如果僅僅要求寫後續遍歷，甚至不要專門佔用空間保存還原後的樹。只需要用一個數組保存將要得到的後序，就能實現：

算法2

輸入：一個保存後序的數組，前序遍歷，中序遍歷

確定根,放在數組末尾
確定左子樹的索引範圍，放在數組中相同索引的位置。
確定右子樹索引範圍，放在數組中對應索引的位置，剛好能放下。
用左子樹的前序遍歷和中序遍歷，把後序遍歷保存在對應索引的位置
用左子樹的前序遍歷和中序遍歷，把後序遍歷保存在對應索引的位置

更多C/C++學習資料，請私信我“代碼”獲取，或群：708219153

引申問題

同樣我們可以用中序遍歷和後序遍歷還原這顆樹。

然而，如果是前序遍歷和後序遍歷，就不能夠還原這棵樹了，因為無法找到中間點，注意下面這兩種情況：

更多C/C++學習資料，請私信我“代碼”獲取，或群：708219153

兩棵樹的前序是相同的，兩棵樹的後序也是相同的。換句話說，如果有一顆子樹，它的根節點的一個子樹是空樹，那麼就無法判定那一個子樹是空樹。

//算法1
#include <iostream>
#include <fstream>
#include <string>
struct TreeNode
{ 

 struct TreeNode* left;
 struct TreeNode* right;
 char elem;
};
TreeNode* BinaryTreeFromOrderings(char* inorder, char* preorder, int length)
{
 if(length == 0)
 {
 return NULL;
 }
 TreeNode* node = new TreeNode;
 node->elem = *preorder;
 int rootIndex = 0;
 for(;rootIndex < length; rootIndex++)
 {
 if(inorder[rootIndex] == *preorder)
 break;
 }
 node->left = BinaryTreeFromOrderings(inorder, preorder +1, rootIndex);
 node->right = BinaryTreeFromOrderings(inorder + rootIndex + 1, preorder + rootIndex + 1, length - (rootIndex + 1));
 std::cout<<node->elem<<:endl>　free(node);
 return NULL;
}
int main(int argc, char** argv){
 char* pr="GDAFEMHZ"; 
 char* in="ADEFGHMZ"; 
 BinaryTreeFromOrderings(in, pr, 8); 
 printf("\n");
 return 0; 
}
 
/<node->/<string>/<fstream>/<iostream>