蟒蛇轉換排序雙鏈表到BST

Question

這個想法是非常相似的其他大多數人，做一個inorder到位遍歷治療左prevNode和右nextNode 因爲某些原因，它只是不能工作..似乎沒有運行遞歸？

我測試了我的DoubleLinked名單是由印刷preNode和nextNode

正確池莉構建，但仍說「NoneType」對象有沒有屬性「VAL」 的問題是buildTree

任何一個plz幫助

class LinkNode(object): 
    def __init__(self, val): 
     self.val = val 
     self.nextNode = None 
     self.prevNode = None 


def buildLinkList(arr): 
    dummy = head = LinkNode(None) 
    dummy.nextNode = head 
    for val in arr: 
     new_node = LinkNode(val) 
     new_node.prevNode = head 
     head.nextNode = new_node 
     head = head.nextNode 
    return dummy.nextNode 

def printLink(head): 
    while head: 
     print head.val 
     if not head.nextNode: 
      #print head.val 
      return head 
     head = head.nextNode 

def buildTree(head, n): 
    if n <= 0: 
     return None 
    left = buildTree(head, n/2) 
    print head.val 
    root = head 
    root.prevNode = left 
    head = head.nextNode 
    root.nextNode = buildTree(head, n - n/2 - 1) 
    return root 


def inorder(root): 
    if root: 
     inorder(root.prevNode) 
     print root.val 
     inorder(root.nextNode) 

arr = [1, 2, 3, 4, 5, 6, 7] 
head = buildLinkList(arr) 
#print head.val 
root = buildTree(head, 7) 

Answer 1

試試這個：

def recursiveMakeDLL(node, prevNode=None): 
    if node is None: 
     return None 

    left = recursiveMakeDLL(node.left, prevNode) 
    node.left = left if left is not None else prevNode 
    if left is not None: 
     left.right = node 
    elif prevNode is not None: 
     prevNode.right = node 

    prevToReturn = recursiveMakeDLL(node.right, node) 
    return prevToReturn if prevToReturn is not None else node 


def makeDLL(root): 
    root = recursiveMakeDLL(root) 
    head = root 
    tail = root 
    while head.left is not None: 
     head = head.left 
    while tail.right is not None: 
     tail = tail.right 
    head.left = tail 
    tail.right = head 

    return head 

這個想法是將prevNode作爲遞歸的一部分傳遞，以便當堆棧從按順序遍歷返回時，我們可以將當前的左側設置爲它的左側。