Easy to understand recursive Python solution

  • 0
    class Solution(object):
        def build(self, preorder, inorder, pi, pj, ii, ij, dp, di):
            if pi > pj: return None
            root = TreeNode(preorder[pi])
            i = di[root.val]
            root.left = self.build(preorder, inorder, pi+1, pi+i-ii, ii, i-1, dp, di)
            root.right = self.build(preorder, inorder, pi+i-ii+1, pj, i+1, ij, dp, di)
            return root
        def buildTree(self, preorder, inorder):
            dp = {}; di = {}
            for i in range(len(preorder)):
                dp[preorder[i]] = i
                di[inorder[i]] = i
            return self.build(preorder, inorder, 0, len(preorder)-1, 0, len(inorder)-1, dp, di)

    2 key remarks:

    • We build a dictionary to have O(1) access to where any node.val is.
    • We pass indices as a parameter to recursive call instead of making a copy of the preorder and inorder lists to prevent memory limit error.

Log in to reply

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