My Python Solution that runs in 55ms


  • 0
    R
    # 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 len(postorder) == 0:
                return None
            stack, index, end = [], len(postorder) - 1, len(postorder) - 2
            root = TreeNode(postorder[index])
            stack.append(root)
            for i in range(end, -1, -1):
                cur = stack[-1]
                if cur.val != inorder[index]:
                    cur.right = TreeNode(postorder[i])
                    stack.append(cur.right)
                else:
                    while len(stack) != 0 and stack[-1].val == inorder[index]:
                        cur = stack[-1]
                        stack.pop()
                        index -= 1
                    if index >= 0:
                        cur.left = TreeNode(postorder[i])
                        stack.append(cur.left)
                i -= 1
            return root
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.