原题地址
思路：
和leetcode105题差不多，这道题是给中序和后序，求出二叉树。
解法一：
思路和105题差不多，只是pos是从后往前遍历，生成树顺序也是先右后左。
class Solution {public:TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {int pos = postorder.size() - 1;return dfs(inorder, postorder, 0, inorder.size(), pos);}private:TreeNode *dfs(vector<int> &inorder, vector<int> &postorder, int beg, int end,int &pos) {TreeNode *node = NULL;if (beg < end) {int i = 0;for (i = beg; i < end; ++i)if (postorder[pos] == inorder[i]) break;pos--;node = new TreeNode(inorder[i]);node->right = dfs(inorder, postorder, i + 1, end, pos);node->left = dfs(inorder, postorder, beg, i, pos);}return node;}
};
解法二：
解法二是看了别人的题解入手的，和解法一不同思路的是对两个序都用一组beg和end来划分区间。
中序（beg,end）很好划分，假设mid指向当前节点的root值，则分为mid前一半和mid后一半。
后序（pbeg,pend）的划分，是mid - beg的这一段距离。
class Solution
{
public:TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder){return dfs(inorder, postorder, 0, inorder.size(), 0, postorder.size());}private:TreeNode *dfs(vector<int> &inorder, vector<int> &postorder, int beg, int end,int pbeg, int pend){TreeNode *node = NULL;if (beg < end){int i = 0;for (i = beg; i < end; ++i)if (postorder[pend - 1] == inorder[i])break;node = new TreeNode(inorder[i]);node->left = dfs(inorder, postorder, beg, i, pbeg, pbeg + i - beg);node->right =dfs(inorder, postorder, i + 1, end, pbeg + i - beg, pend - 1);}return node;}
};
解法一好理解，但是速度慢，用了16ms，击败46%
解法二难点在于理解后序区间划分的依据，用了12ms，击败78%
虽然做了105题，但是做这题还是花了一个半小时。
还是因为不够深入的理解原理，不能总是光看题解就过了。