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


  • 0
    T

    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)
                inord.pop()
                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.