Construct Binary Tree from Inorder and Postorder Traversal

#O(N) worst case solution with right subtree construction first

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        inorder = {val: i for i, val in enumerate(inorder)}

        def construct(beg, end):
            if end - beg < 0:
                return None

            root = postorder.pop()
            idx = inorder[root]
            node = TreeNode(root)

            node.right = construct(idx+1, end)
            node.left = construct(beg, idx-1)
            return node

        root = construct(0, len(inorder)-1)
        return root
"""
Alternative AC Solutions:
O(N) worst case with left subtree construction first

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def buildTree(self, inorder, postorder):

        inorder = {val: i for i, val in enumerate(inorder)}

        def construct(ibeg, iend, pbeg, pend):
            if iend - ibeg < 0:
                return None

            root = postorder[pend]
            idx = inorder[root]
            node = TreeNode(root)

        #left = idx - ibeg
        #right = iend - idx

            node.left = construct(ibeg, idx-1, pbeg, pbeg + idx - ibeg - 1)
            node.right = construct(idx+1, iend, pend-iend + idx, pend-1)
            return node

        root = construct(0, len(inorder)-1, 0, len(postorder)-1)
        return root

O(N2) worst case

class Solution(object):
    def buildTree(self, inorder, postorder):

        pOrder = {val: i for i, val in enumerate(postorder)}

        def construct(iOrder):
            if len(iOrder) == 0:
                return None

            maxidx = 0
            for i, e in enumerate(iOrder):
                if pOrder[e] > pOrder[iOrder[maxidx]]:
                    maxidx = i
            node = TreeNode(iOrder[maxidx])

            node.left = construct(iOrder[:maxidx])
            node.right = construct(iOrder[maxidx+1:])
            return node

        root = construct(inorder)
        return root
"""