Runtime Error? [Python]


  • 1
    Z
    class Solution:
        # @param head, a list node
        # @return a tree node
        def sortedArrayToBST(self, num):
            if len(num) == 0: 
                return None
            mid = len(num)//2
            current = TreeNode(num[mid])
            current.left = self.sortedArrayToBST(num[:mid])
            current.right = self.sortedArrayToBST(num[mid+1:])
            return current 
            
        def sortedListToBST(self, head):
            array = []
            p = head
            while head: 
                array.append(p.val)
                p = p.next 
            return self.sortedArrayToBST(array)
    

    I convert sorted list to an sorted array and use the previous function to solve the problem. OJ says: Line 30: AttributeError: 'NoneType' object has no attribute 'val'. I don't know what's wrong with 'array.append(p.val)'... Someone please help. Thanks a lot!!


  • 2
    V

    In line 30, p.val is called, but in the while loop p != None condition is not checked hence AttributeError has occurred as when p becomes None val attribute is accessed.

    class Solution:
        # @param head, a list node
        # @return a tree node
        def sortedArrayToBST(self, num):
            if len(num) == 0: 
                return None
            mid = len(num)//2
            current = TreeNode(num[mid])
            current.left = self.sortedArrayToBST(num[:mid])
            current.right = self.sortedArrayToBST(num[mid+1:])
            return current 
    
        def sortedListToBST(self, head):
            array = []
            #check whether p is None
            p = head
            while p!=None: 
                array.append(p.val)
                p = p.next 
            return self.sortedArrayToBST(array)

  • 0
    C

    Yes, when you are passing the array as parameter you can pass the start and end indexes as well, in this way you don't need to compute the length of the sublists:

    def sortedListToBST1(self, head):
        ls = []
        while head:
            ls.append(head.val)
            head = head.next
        return self.helper(ls, 0, len(ls)-1)
    
    def helper(self, ls, start, end):
        if start > end:
            return None
        if start == end:
            return TreeNode(ls[start])
        mid = (start+end) >> 1
        root = TreeNode(ls[mid])
        root.left = self.helper(ls, start, mid-1)
        root.right = self.helper(ls, mid+1, end)
        return root

Log in to reply
 

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