106. Construct Binary Tree from Inorder and Postorder Traversal

题目

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

本题思路和我前面一篇结题报告：105. Construct Binary Tree from Preorder and Inorder Traversal思路一致。可以说是没有差别。这里就不细致分析了

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        //step1:construct hash-tab
        if(postorder.size()==0)
            return NULL;
        unordered_map<int,int> mapIndex;
        for(int i=0;i<inorder.size();i++)
            mapIndex[inorder[i]] = i;
        return helpTree(postorder,0,inorder.size(),0,mapIndex);
    }
private:
    TreeNode* helpTree(vector<int>& postorder,int start,int len,int offest,unordered_map<int,int>& mapIndex)
    {
        if(len<=0)
            return NULL;
        int rootval = postorder[len-1+start];//vist root 
        int i = mapIndex[rootval]-offest;//compute len of left tree
        TreeNode* root = new TreeNode(rootval);
        root->left = helpTree(postorder,start,i,offest,mapIndex);//construct left subtree
        root->right = helpTree(postorder,start+i,len-i-1,offest+i+1,mapIndex);//construct right subtree
        return root;
    }
};