将二进制树转换为双链接列表-Python-错误消息

Question

请帮助我解决leetcode问题 contract搜索树到分类的双链接列表：

将二进制搜索树转换为到位的圆形双关联列表。

您可以将左右指针视为在双连接列表中的前身和后继指针的代名词。对于圆形双链接列表，第一个元素的前身是最后一个元素，最后一个元素的后继是第一个元素。

我正在尝试解决它 - 我不以最佳方式知道 - 但我至少想获得有效的答案。在我看来，列表已对其进行排序，并且是双重链接的，并且指针指向正确的值，但我无法获得正确的解决方案。

我遇到了错误：

链接列表[1,2,3,4,5]不是有效的圆形双链接列表。

以下是我的代码

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inOrderTraversal(node, array):
    if node == None:
        return

    inOrderTraversal(node.left, array)
    array.append(node.val)
    inOrderTraversal(node.right, array)
    return array


class Solution:
    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if root is None:
            return None
        array = []
        inOrderTraversal(root, array)

        head = Node(array[0])
        head.left = Node(array[-1])
        prev_node = head

        for i in range(1, len(array)):
            num = array[i]
            node = Node(num)


            prev_node.right = node     
            node.left = prev_node
            prev_node = node

            if i == len(array) - 1:
                node.right = head


        count = 0
        node = head
        while count < 5:
            print("new Test")
            print(node)
            print(node.left.val)
            print(node.right.val)
            node = node.right
            count += 1

       # print(head.right.val)

        return head

打印输出是：

new Test
<__main__.Node object at 0x7f0318a062c0>
5
2
new Test
<__main__.Node object at 0x7f0318a06a40>
1
3
new Test
<__main__.Node object at 0x7f0318a06c20>
2
4
new Test
<__main__.Node object at 0x7f0318a3e680>
3
5
new Test
<__main__.Node object at 0x7f0318a3e6e0>
4
1

我添加了此输出，以确保双链接列表很好，但是测试框架表示不是。

当我将BST作为1、2、3、4、5作为值的输入时，生成的双链接列表在哪里错误？

Answer 1

问题是head.left是分配的节点实例，它不是在循环的最后一次迭代中创建的节点。因此，您有两个尾部节点。看到某事物的另一种方法是计算您调用node（）的次数：这是一次太多。

然后，当您向前浏览列表时，一切都可以，但是当您从head向后走到上一个节点时，该节点的left属性仍然是无。

解决方案是从您的代码中删除这一行：

    head.left = Node(array[-1])

以及这些行中的这些行 - 它们并没有错，但是在之后进行操作是更自然的， 已经完成：

      if i == len(array) - 1:
            node.right = head

现在在循环之后，执行此操作（node是列表中的 last 节点）：

    node.right = head
    head.left = node

一些改进的想法

• turn inordertraversal进入发电机。

• 利用节点构造函数通过其参数

  设置left属性的功能

def inOrderTraversal(node):
    if node == None:
        return
    yield from inOrderTraversal(node.left)
    yield node.val
    yield from inOrderTraversal(node.right)


class Solution:
    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if root is None:
            return
        iterator = inOrderTraversal(root)
        head = Node(next(iterator))
        prev_node = head

        for val in iterator:
            node = Node(val, prev_node)
            prev_node.right = node     
            prev_node = node

        node.right = head
        head.left = node
        return head