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

Question

I am very confused about the question No.426 on leetcode, as I think my answer is right. But after running it shows I am wrong. Below is the question and my original answer:

"""
# 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

Could someone help me to figure out what's wrong with my codes? Any comment or suggestion will be so appreciated.

Answer 1

I see two problems with the code.

First is that inside your if sign: block you need to set sign = False since you only want to initialize head once and execute that block only the first time. (Not sure why the variable is called sign, perhaps first would be more appropriate, or just reusing a head = None for that condition would have worked too.)

The second bug is smaller and affects the last link in the list to make it circular. You want to set pre.right = head instead of pre, so that the last node of the list points back at the first, not at itself.

I haven't really tested this, so it's possible I'm missing something, but it looks to me that this should be enough to fix this code.