lc426.将二叉搜索树转化为排序的双向列表

"""
# 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 
        self.pre = None
        self.dfs(root)
        self.head.left, self.pre.right = self.pre, self.head
        return self.head

    def dfs(self, cur):
        if not cur:
            return 
        self.dfs(cur.left)
        if self.pre:
            self.pre.right, cur.left = cur, self.pre
        else:
            self.head = cur
        self.pre = cur
        self.dfs(cur.right)