Leetcode 426. 将二叉搜索树转换为有序双向链表？

Question

我对leetcode上的426号题很疑惑，我觉得我的答案是对的。但是在运行之后，它表明我错了。以下是问题和我的原始答案：

"""
# Definition for a Node.
class Node:
    def __init__(self, val, left, right):
        self.val = val
        self.left = left
        self.right = right
"""
class Solution:
    def treeToDoublyList(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        if root:
            sign = True
            stack = []
            node = root

            while stack or node:
                if node:
                    stack.append(node)
                    node = node.left 
                else:
                    node = stack.pop()

                    if sign:
                        pre,head = node, node
                    else:
                        pre.right = node
                        node.left = pre
                        pre = node

                    node = node.right

            head.left = pre
            pre.right = pre

            return head
        else:
            return None

有人可以帮我弄清楚我的代码有什么问题吗？如有任何意见或建议，我们将不胜感激。

Answer 1

我发现代码有两个问题。

首先是在您的 if sign: 块中您需要设置 sign = False 因为您只想初始化一次 head 并且只在第一次执行该块。（不确定为什么将变量称为 sign，也许 first 更合适，或者只是为该条件重用 head = None 也可以。）

第二个错误较小，影响列表中的最后一个 link，使其循环。您想要设置 pre.right = head 而不是 pre，以便列表的最后一个节点指向第一个节点，而不是它本身。

我还没有真正测试过这个，所以我可能遗漏了一些东西，但在我看来这应该足以修复这段代码。

Leetcode 426. 将二叉搜索树转换为有序双向链表？

Leetcode 426. Convert Binary Search Tree to Sorted Doubly Linked List?

python

inorder

binary-search-tree

doubly-linked-list