将二叉查找树变为有序的双向链表

以下是两种将二叉查找树变为有序的双向链表的方法：

方法一：递归实现

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def treeToDoublyList(self, root: 'TreeNode') -> 'TreeNode':
        if not root:
            return None
        self.temp = None
        self.dfs(root)
        self.head.left = self.temp
        self.temp.right = self.head
        return self.head

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

方法二：非递归实现

class Solution:
    def treeToDoublyList(self, root: 'TreeNode') -> 'TreeNode':
        if not root:
            return None
        stack = []
        cur = root
        pre = None
        head = None
        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            if not head:
                head = cur
            if pre:
                pre.right = cur
                cur.left = pre
            pre = cur
            cur = cur.right
        pre.right = head
        head.left = pre
        return head