**一. 題目描述** Given inorder and postorder traversal of a tree, construct the binary tree.? Note: You may assume that duplicates do not exist in the tree. **二. 題目分析** 這道題和Construct Binary Tree from Preorder and Inorder Traversal類似，都是考察基本概念的，后序遍歷是先遍歷左子樹，然后遍歷右子樹，最后遍歷根節點。 做法都是先根據后序遍歷的概念，找到后序遍歷最后的一個值，即為根節點的值，然后根據根節點將中序遍歷的結果分成左子樹和右子樹，然后就可以遞歸的實現了。 上述做法的時間復雜度為`O(n^2)`，空間復雜度為`O(1)`。 **三. 示例代碼** ~~~ #include <iostream> #include <algorithm> #include <vector> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { private: TreeNode* buildTree(vector<int>::iterator PostBegin, vector<int>::iterator PostEnd, vector<int>::iterator InBegin, vector<int>::iterator InEnd) { if (InBegin == InEnd) { return NULL; } if (PostBegin == PostEnd) { return NULL; } int HeadValue = *(--PostEnd); TreeNode *HeadNode = new TreeNode(HeadValue); vector<int>::iterator LeftEnd = find(InBegin, InEnd, HeadValue); if (LeftEnd != InEnd) { HeadNode->left = buildTree(PostBegin, PostBegin + (LeftEnd - InBegin), InBegin, LeftEnd); } HeadNode->right = buildTree(PostBegin + (LeftEnd - InBegin), PostEnd, LeftEnd + 1, InEnd); return HeadNode; } public: TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { if (inorder.empty()) { return NULL; } return buildTree(postorder.begin(), postorder.end(), inorder.begin(), inorder.end()); } }; ~~~ **四. 小結** 與前面一題一樣，該題考察了基礎概念，并不涉及過多的算法問題。