Python recursive solution in O(n) time and O(1) space

  • 0

    This is an extension of StefanPochmann's brilliant solution to the construct-binary-tree-from-preorder-and-inorder-traversal problem.

    def buildTree(self, inorder, postorder):
        def build(stopper, inord, postord):
            if inord and inord[-1] != stopper:
                root = TreeNode(postord.pop())
                root.right = build(root.val, inord, postord)
                root.left = build(stopper, inord, postord)
                return root
        return build(None, inorder, postorder)

    In the original solution, we process in the order: root, left and right while constructing the solution. Just use the order: root, right and left instead.

Log in to reply

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