426. Convert Binary Search Tree to Sorted Doubly Linked List - cocoder39/coco39_LC GitHub Wiki

426. Convert Binary Search Tree to Sorted Doubly Linked List

2024: in order traversal without stack

class Solution:
    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root:
            return root

        head = Node(0)
        tail = self.helper(root, head)
        tail.right = head.right
        head.right.left = tail
        return head.right
    
    def helper(self, cur_node, pre_node):
        if cur_node.left:
            pre_node = self.helper(cur_node.left, pre_node)
        
        cur_node.left = pre_node
        pre_node.right = cur_node
        pre_node = cur_node

        if cur_node.right:
            pre_node = self.helper(cur_node.right, pre_node)
        
        return pre_node

====================

sorted => in-order traversal

class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root:
            return None
        
        dummy = Node(0)
        dummy.right = root
        
        stack = []
        prev = dummy
        while root or stack:
            if root:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                root.left = prev
                prev.right = root
                prev = root
                #print(root.val)
                root = root.right   
        prev.right = dummy.right
        prev.right.left = prev
        
        return dummy.right