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

本题给定中序排列和后序排列，求二叉树。

后序排列的顺序是：左节点——右节点——根节点。

和105题一样，将后序排列的最后一位视作根节点的val值即可。

class Solution {

public:

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {

        return work(inorder, postorder, 0, inorder.size()-1, 0, postorder.size()-1);

    }

    TreeNode* work(vector<int>& inorder, vector<int>& postorder, int inleft, int inright, int postleft, int postright){

        if(inleft>inright) return NULL;

        TreeNode *root = new TreeNode(postorder[postright]);

        for(int k=inleft; k<=inright; k++){

            if(inorder[k] == postorder[postright]){

                root->left = work(inorder, postorder, inleft, k-1, postleft, postleft+k-inleft-1);

                root->right = work(inorder, postorder, k+1, inright, postleft+k-inleft, postright-1);

            }

        }

        return root;

    }

};