Python 8lines O(n) time without extra space or split array, beats 98%


  • 0

    Based on @StefanPochmann 's brilliant idea on Simple O(n) without map.

    class Solution(object):
        def buildTree(self, inorder, postorder):
            """
            :type inorder: List[int]
            :type postorder: List[int]
            :rtype: TreeNode
            """
            def build(stop):
                if inorder and inorder[-1] != stop:
                    root = TreeNode(postorder.pop())
                    root.right = build(root.val)
                    inorder.pop()
                    root.left = build(stop)
                    return root
            return build(None)
    

Log in to reply
 

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