106. 从中序与后序遍历序列构造二叉树

class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        # 用字典存储中序序列中root的值与下标
        myDict = {v: i for i, v in enumerate(inorder)}
        return self.dg(0, len(inorder) - 1, postorder, 0, len(postorder) - 1, myDict)

    def dg(self, inLeft, inRight, postorder, postLeft, postRight, myDict):
        if inLeft > inRight or postLeft > postRight:
            return
        rootVal = postorder[postRight]
        rootIndex = myDict[rootVal]
        root = TreeNode(rootVal)
        root.left = self.dg(inLeft, rootIndex - 1, postorder, postLeft, rootIndex - 1 - inLeft + postLeft, myDict)
        root.right = self.dg(rootIndex + 1, inRight, postorder, rootIndex - inLeft + postLeft, postRight - 1, myDict)
        return root