将二叉搜索树转化为排序的双向链表

标签: 栈 树 深度优先搜索 二叉搜索树 链表 二叉树 双向链表

难度: Medium

将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。

对于双向循环列表，你可以将左右孩子指针作为双向循环链表的前驱和后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

特别地，我们希望可以 就地 完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中最小元素的指针。

示例 1：

输入：root = [4,2,5,1,3] 


输出：[1,2,3,4,5]

解释：下图显示了转化后的二叉搜索树，实线表示后继关系，虚线表示前驱关系。

示例 2：

输入：root = [2,1,3]
输出：[1,2,3]

示例 3：

输入：root = []
输出：[]
解释：输入是空树，所以输出也是空链表。

示例 4：

输入：root = [1]
输出：[1]

提示：

  • -1000 <= Node.val <= 1000
  • Node.left.val < Node.val < Node.right.val
  • Node.val 的所有值都是独一无二的
  • 0 <= Number of Nodes <= 2000

注意：本题与主站 426 题相同：https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/

Submission

运行时间: 36 ms

内存: 16 MB

"""
# 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 __init__(self):
        self.pre = None
        self.head = None

    def treeToDoublyList(self, root: 'Node') -> 'Node':
        def dfs(cur):
            if cur is None:
                return
            dfs(cur.left)
            if self.pre is None:
                self.head = cur
            else:
                self.pre.right = cur
                cur.left = self.pre
            self.pre = cur
            dfs(cur.right)

        if root is None:
            return
        dfs(root)
        self.head.left, self.pre.right = self.pre, self.head
        return self.head

Explain

这个题解采用了中序遍历（In-order traversal）的方式来处理二叉搜索树，将其转化为双向循环链表。由于二叉搜索树的中序遍历可以按照从小到大的顺序访问所有节点，这个特性被用于正确地设置链表中节点的前驱和后继关系。在遍历过程中，维护一个指针pre来指向当前节点的前一个节点，用于建立当前节点的前驱链接。当遍历访问到树的最左侧节点时，将其设置为双向循环链表的头节点head。在完成整个树的遍历后，将头节点的前驱设置为最后一个访问的节点，且将最后一个节点的后继设置为头节点，从而完成双向循环链表的闭环。

时间复杂度: O(n)

空间复杂度: O(n)

"""
# 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 __init__(self):
        self.pre = None  # 用于记录上一个访问的节点
        self.head = None  # 链表的头节点

    def treeToDoublyList(self, root: 'Node') -> 'Node':
        def dfs(cur):
            if cur is None:
                return  # 递归终止条件
            dfs(cur.left)  # 访问左子树
            if self.pre is None:
                self.head = cur  # 确定链表头节点
            else:
                self.pre.right = cur  # 设置前一个节点的后继为当前节点
                cur.left = self.pre  # 设置当前节点的前驱为前一个节点
            self.pre = cur  # 更新前一个节点为当前节点
            dfs(cur.right)  # 访问右子树

        if root is None:
            return  # 处理空树的情况
        dfs(root)  # 从根节点开始中序遍历
        self.head.left, self.pre.right = self.pre, self.head  # 完成双向循环链表的头尾连接
        return self.head  # 返回链表的头节点

"""

Explore

二叉搜索树的中序遍历能够按照从小到大的顺序访问所有节点。在遍历的过程中，每个节点都按照这一顺序被处理，前一个访问的节点（通过'pre'指针记录）总是比当前节点小。当我们将'pre'的'right'指向当前节点，同时将当前节点的'left'指向'pre'，我们正是在利用这一顺序性来正确设置双向链表中每个节点的前驱和后继关系，从而保证转化出的双向链表维持了二叉搜索树的顺序性。

如果二叉搜索树为空，没有任何节点可以转换成双向链表。在这种情况下，根据题解中的逻辑，函数会直接返回None。因此，当二叉搜索树为空时，返回的双向链表头节点也是None。

当二叉搜索树只有一个节点时，这个节点既是头节点也是尾节点。在中序遍历中，这个节点会被设置为'head'，同时由于没有其他节点，'pre'仍然是None，直到这个节点本身被处理。在处理结束时，我们将这个节点的'left'和'right'都指向自身，从而形成一个只包含单个节点的循环双向链表。

'pre'指针的初始值为None是用来标识链表头部的设置以及第一个节点的处理。在遍历的开始，没有前一个节点，因此'pre'为None可以帮助我们识别并设置第一个访问的节点（二叉搜索树最左侧的节点）为双向链表的头节点。此外，当'pre'仍然为None时，我们不会尝试设置任何节点的'left'链接，这避免了对非存在节点的引用。一旦第一个节点被处理，'pre'将不再是None，之后的每个节点都能正确地链接到前一个节点。