A Python recursive solution


  • 12
    G

    The idea is to find the root first, and then recursively build each left and right subtree

    Only Solution 3 could pass the OJ, but theoretically they should all work ...

    Solution 1 - clean and easy to understand, but Memory Limit Exceeded ...

    # Definition for a  binary tree node
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        # @param preorder, a list of integers
        # @param inorder, a list of integers
        # @return a tree node
        # 1:59
        def buildTree(self, preorder, inorder):
            if not preorder or not inorder:
                return None
            
            rootValue = preorder[0]
            root = TreeNode(rootValue)
            inorderIndex = inorder.index(rootValue)
    
            root.left = self.buildTree(preorder[1:inorderIndex+1], inorder[:inorderIndex])
            root.right = self.buildTree(preorder[inorderIndex+1:], inorder[inorderIndex+1:])
            
            return root
    

    Solution 2 - Same as solution one, but pass index instead of doing list slicing (and thus reduce the memory usage)

    class Solution:
        # @param preorder, a list of integers
        # @param inorder, a list of integers
        # @return a tree node
        # 1:59
        def buildTree(self, preorder, inorder, preorderStart = 0, preorderEnd = None, inorderStart = 0, inorderEnd = None):
            if preorderEnd is None:
                preorderEnd = len(preorder) - 1
            
            if inorderEnd is None:
                inorderEnd = len(inorder) - 1
    
            if preorderStart > len(preorder) - 1 or inorderStart > inorderEnd:
                return None
            
            rootValue = preorder[preorderStart]
            root = TreeNode(rootValue)
            inorderIndex = inorder.index(rootValue)
    
            root.left = self.buildTree(preorder, inorder, preorderStart+1, inorderIndex, inorderStart, inorderIndex-1)
            root.right = self.buildTree(preorder, inorder, preorderStart+inorderIndex+1-inorderStart, preorderEnd, inorderIndex+1, inorderEnd)
            
            return root
    

    Solution 3 - Based on Solution 1, we don't necessary need to slice the preorder array, when we are done with the left tree, the left half of the preorder array should already be empty

    # Definition for a  binary tree node
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        # @param preorder, a list of integers
        # @param inorder, a list of integers
        # @return a tree node
        # 1:59
        def buildTree(self, preorder, inorder):
            if not preorder or not inorder:
                return None
    
            rootValue = preorder.pop(0)
            root = TreeNode(rootValue)
            inorderIndex = inorder.index(rootValue)
    
            root.left = self.buildTree(preorder, inorder[:inorderIndex])
            root.right = self.buildTree(preorder, inorder[inorderIndex+1:])
    
            return root

  • 0
    S

    why it says runtime error? It works fine on simple examples and should be working on large data sets too. hum....


  • 0
    G

    Well, I didn't really run the solution 2 in oj ... That's why I just added solution 3 :p


  • 0
    G

    And yes, I did run solution 3 in OJ and it passed lol


  • 0
    G

    The runtime error is because maximum recursion depth exceeded


  • 2

    Simpler base-case-handling, if inorder is enough:

    def buildTree(self, preorder, inorder):
        if inorder:
            root = TreeNode(preorder.pop(0))
            inorderIndex = inorder.index(root.val)
            root.left = self.buildTree(preorder, inorder[:inorderIndex])
            root.right = self.buildTree(preorder, inorder[inorderIndex+1:])
            return root
    

    Btw, what does the 1:59 mean? I've noticed I think 1:40 in another solution of yours before...


  • 0
    L

    pop(0) is O(n) so the complexity is n^2?


  • 0

    Although solution 3 passes the system I still doubt that it consumes quite a lot of memory for always creating the latter half array. The optimal way for recursion should still be using indices.


Log in to reply
 

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