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 Ignorer Traversal類似，只是把前序遍歷數(shù)組改為后續(xù)遍歷數(shù)組，要求我們在給定二叉樹的后續(xù)遍歷數(shù)組和中序遍歷數(shù)組的情況下，構(gòu)造二叉樹?；舅悸啡缦拢?/p>

• 后續(xù)遍歷數(shù)組的最后一個(gè)數(shù)preorder[n]就是二叉樹的根節(jié)點(diǎn)
• 遍歷中序數(shù)組，找到根節(jié)點(diǎn)，假設(shè)為inorder[i]
• 假定數(shù)組的長度為n, 則inorder[0]...inorder[i-1]構(gòu)成左子樹，inorder[i+1]...inorder[n]構(gòu)成右子樹。
• 重復(fù)以上過程，即可構(gòu)造二叉樹。

具體代碼如下：

class Solution {
public:
    TreeNode* buildTreeHelper(int postEnd, int inStart, int inEnd, vector<int>& inorder, vector<int>& postorder)
    {
        if(postEnd < 0 || inStart > inEnd) return NULL;
        TreeNode * root = new TreeNode(postorder[postEnd]);
        int index = 0;
        for(int i = 0; i < inorder.size(); ++i)
        {
            if(postorder[postEnd] == inorder[i])
                index = i;
        }
        root->left = buildTreeHelper(postEnd - (inEnd - index) - 1, inStart, index - 1, inorder, postorder);
        root->right = buildTreeHelper(postEnd - 1, index + 1, inEnd,inorder,postorder);
        return root;
    }
    
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return buildTreeHelper(postorder.size() - 1, 0, inorder.size() - 1, inorder, postorder);
    }
};