**一. 题目描述** 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()); } }; ~~~ **四. 小结** 与前面一题一样，该题考察了基础概念，并不涉及过多的算法问题。