426. Convert Binary Search Tree to Sorted Doubly Linked List (Medium) - TengnanYao/daily_leetcode GitHub Wiki

"""
# Definition for a Node.
class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
"""

class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root:
            return None
        nodes = []
        def dfs(root):
            if root:
                dfs(root.left)
                nodes.append(root)
                dfs(root.right)
        dfs(root)
        nodes.append(nodes[0])
        for i in range(len(nodes) - 1):
            node1, node2 = nodes[i], nodes[i + 1]
            node1.right, node2.left = node2, node1
        return nodes[0]