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.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

---

本题要根据树的中序和后序遍历结果，重构出树的结构。 有了之前LeetCode Construct Binary Tree from Preorder and Inorder Traversal根据前序和中序重构树的算法，这一题就是照猫画虎了。因为后序遍历是最后一个数为根节点，和前序遍历其实没本质差别。找准inorder和postorder下标的起止位置就可以开始写代码了：

class Solution {
private:
    TreeNode* dfs(vector<int>& inorder, vector<int>& postorder, int inL, int inR, int postL, int postR, unordered_map<int, int>& hash)
    {
        if (inL > inR || postL > postR)
            return NULL;
        TreeNode* root = new TreeNode(postorder[postR]);
        int idx = hash[root->val];
        root->right = dfs(inorder, postorder, inL + 1, inR, postR – (inR – idx), postR – 1, hash);
        root->left = dfs(inorder, postorder, inL, idx – 1, postL, postR – (inR – idx) – 1, hash);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
    {
        if (inorder.size() == 0)
            return NULL;
        unordered_map<int, int> hash;
        for (int i = 0; i < inorder.size(); ++i) {
            hash[inorder[i]] = i;
        }
        return dfs(inorder, postorder, 0, inorder.size() – 1, 0, postorder.size() – 1, hash);
    }
};

本代码提交AC，用时16MS。