Leetcode 426. Преобразовать двоичное дерево поиска в отсортированный двусвязный список?

Question

Я очень озадачен вопросом № 426 о коде leet, так как я думаю, что мой ответ правильный.Но после запуска это показывает, что я не прав.Ниже приведен вопрос и мой оригинальный ответ:

"""
# 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 для этого условия тоже сработало бы.)

Вторая ошибка меньше и влияетпоследняя ссылка в списке, чтобы сделать ее круглой.Вы хотите установить pre.right = head вместо pre, чтобы последний узел списка указывал на первый, а не на саму себя.

Я на самом деле не проверял это, так что возможно я 'Я что-то упустил, но мне кажется, что этого должно быть достаточно, чтобы исправить этот код.