本文共 2649 字，大约阅读时间需要 8 分钟。

题目

例如，给出

返回如下的二叉树：

思路

从中序和后序生成原理可知，后序遍历中的最后一个元素即为root节点，则该节点对应到中序遍历中又把中序遍历划分为左右子树，这两个左右子树又反过来对应各自的后序遍历。(即元素3将中序遍历划分为[9]和[15,20,7]两个子树，这两个子树对应后序遍历又可以推出子树的root节点)。

分析可知，二叉树的构造存在重复的子问题，则可使用递归来解决问题。我们只需要通过后序遍历的最后一个元素，就可以通过中序定位该元素的左右子树，则左右子树又是一个由中序和后序遍历构造还原二叉树的过程。

class Solution {   public:    unordered_map
   
     map;//通过键值对得到每个数的位置    TreeNode* buildTree(vector
    
     & inorder, vector
     
      & postorder) {           if(inorder.empty()) return NULL;        for(int i = 0; i < inorder.size(); i++){               map[inorder[i]] = i;//给出int值对应的位置  数值-位置(从0开始)        }        return build(inorder, postorder, 0 ,postorder.size()-1, 0, postorder.size()-1);    }    TreeNode* build(vector
      
       & inorder, vector
       
        & postorder, int rf, int lf, int rs, int ls)    {           if(rf > lf) return NULL;        TreeNode *root = new TreeNode(postorder[ls]);        int position = map[postorder[ls]];        root->left = build(inorder, postorder, rf, position-1, rs, position-1);//注意这里的rf rs不能用0代替！！！        root->right = build(inorder, postorder, position+1, lf, rs+position, ls-1);//这里的rs不是position 他是每次在分类后的position位置叠加        return root;    }};
       
      
     
    
   

首先要分析递归函数需要接受什么参数，中序和后序遍历向量肯定需要，而且在不断的分割向量时，需要明确新产生的中序和后序遍历，如果采用拷贝传递额外消耗了内存，依旧可以使用原始遍历，只要给出对应所在的位置即可，这样的话明确了传递2个向量，4个int确定位置(两个向量的首尾)。

第一次 ：首先通过postorder最后一个元素postorder.size()-1，则在inorder对应的position划分为两个部分，那么两部分分别是[0,position-1]和[position+1,postorder.size()-1]。对于第一次划分没有错。

注意：第一次划分的写法十分不严谨，因为在后序的划分中中序遍历的左子树起始位置不都是0，这就导致递归过程中的范围错误，使用递归必须明确通项写法！类似数学归纳法的通项！上面的写法并非通项带入到代码中肯定会产生错误，因为后序的中序遍历不会总是从0开始！！！！这里将是常犯错误一定要注意规避！

修改后的代码：

class Solution {   public:    unordered_map
   
     map;//通过键值对得到每个数的位置    TreeNode* buildTree(vector
    
     & inorder, vector
     
      & postorder) {           if(inorder.empty()) return NULL;        for(int i = 0; i < inorder.size(); i++){               map[inorder[i]] = i;//给出int值对应的位置  数值-位置(从0开始)        }        return build(inorder, postorder, 0 ,postorder.size()-1, 0, postorder.size()-1);    }    TreeNode* build(vector
      
       & inorder, vector
       
        & postorder, int rf, int lf, int rs, int ls)    {           if(rf > lf) return NULL;        TreeNode *root = new TreeNode(postorder[ls]);        int position = map[postorder[ls]];        root->left = build(inorder, postorder, rf, position-1, rs, position-1+rs-rf);//注意这里的rf rs不能用0代替！！！        root->right = build(inorder, postorder, position+1, lf, rs+position-rf, ls-1);//这里的rs不是position 他是每次在分类后的position位置叠加        return root;    }};