import BinaryTreeRepresentation


class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    # Op1 O(n logn) -> O(n^2) 176ms
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        if inorder:
            pos = inorder.index(postorder.pop())
            root = TreeNode(inorder[pos])
            root.right = self.buildTree(inorder[pos+1:], postorder)
            root.left = self.buildTree(inorder[:pos], postorder)
            # print(root.val, end=' ')
            return root

    # Op2 O(n) 84ms
    def buildTree2(self, inorder, postorder):
        self.dic = dict((x, i) for i, x in enumerate(inorder))
        self.indexPost = len(postorder) - 1
        return self.helper(postorder, 0, len(postorder) - 1)

    def helper(self, postorder, start, end):
        if start > end or self.indexPost < 0:
            return None
        root = TreeNode(postorder[self.indexPost])
        self.indexPost -= 1
        indexIn = self.dic[root.val]
        root.right = self.helper(postorder, indexIn + 1, end)
        root.left = self.helper(postorder, start, indexIn - 1)
        return root


test = Solution()
root = test.buildTree2(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'], ['A', 'C', 'E', 'D', 'B', 'H', 'I', 'G', 'F'])
BinaryTreeRepresentation.drawtree(root)
