PU Construct Binary Tree from Inorder and Postorder Traversal

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        if not inorder: return None
        roots = []
        stack = []
        i = p = 0
        while p < len(inorder):
            cur_post_val = postorder[p]
            if roots and roots[-1] == cur_post_val:
                rt = TreeNode(cur_post_val)
                rt.right = stack.pop()
                rt.left = stack.pop()
                stack.append(rt)
                roots.pop()
                p += 1
            else:
                cur_in_val = inorder[i]
                if cur_in_val == cur_post_val:
                    i += 1
                    p += 1
                    if len(roots) == len(stack):
                        stack.append(TreeNode(cur_post_val))      
                    else:
                        rt = TreeNode(cur_post_val)
                        rt.left = stack.pop()
                        stack.append(rt)
                else: 
                    if len(roots) == len(stack):
                        stack.append(None)
                    roots.append(cur_in_val)
                    i += 1
        return stack[0]

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        d = {val: key for key, val in enumerate(inorder)}
        def build(istart, iend, pstart, pend):
            if istart > iend: return None
            rt = TreeNode(postorder[pend])
            mid = d[postorder[pend]]
            rt.left = build(istart, mid - 1, pstart, pstart + mid - 1 - istart)
            rt.right = build(mid + 1, iend, pstart + mid - istart, pend - 1)
            return rt
        return build(0, len(inorder) - 1, 0, len(postorder) - 1)