LeetCode如何实现二叉搜索树与双向链表

引言

二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，它具有以下性质：

• 左子树上所有节点的值均小于它的根节点的值。
• 右子树上所有节点的值均大于它的根节点的值。
• 左右子树也分别为二叉搜索树。

双向链表（Doubly Linked List）是一种链表数据结构，每个节点包含两个指针，分别指向前一个节点和后一个节点。

在某些场景下，我们需要将二叉搜索树转换为双向链表。本文将详细介绍如何在LeetCode上实现这一操作，并分析其时间复杂度和空间复杂度。

问题描述

LeetCode上有一道经典的题目：426. Convert Binary Search Tree to Sorted Doubly Linked List。题目要求将一棵二叉搜索树转换为一个有序的双向循环链表。

示例

给定一棵二叉搜索树：

    4
   / \
  2   5
 / \
1   3

将其转换为双向链表后，结果应为：

1 <-> 2 <-> 3 <-> 4 <-> 5

并且链表的头节点和尾节点应该相互连接，形成一个循环链表。

解题思路

要将二叉搜索树转换为有序的双向链表，我们可以利用二叉搜索树的中序遍历性质。中序遍历二叉搜索树会得到一个有序的节点序列。我们可以在这个遍历过程中，逐步构建双向链表。

步骤

1. 中序遍历：对二叉搜索树进行中序遍历，得到一个有序的节点序列。
2. 构建双向链表：在遍历过程中，将当前节点与前一个节点进行连接，形成双向链表。
3. 处理循环链表：最后将链表的头节点和尾节点连接起来，形成循环链表。

具体实现

我们可以使用递归或迭代的方法来实现中序遍历。下面分别介绍这两种方法。

递归方法

递归方法的核心思想是利用中序遍历的顺序，依次访问每个节点，并在访问过程中构建双向链表。

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
        
        # 初始化前驱节点和头节点
        self.prev = None
        self.head = None
        
        # 中序遍历
        self.inorder(root)
        
        # 连接头尾节点形成循环链表
        self.head.left = self.prev
        self.prev.right = self.head
        
        return self.head
    
    def inorder(self, node):
        if not node:
            return
        
        # 递归左子树
        self.inorder(node.left)
        
        # 处理当前节点
        if self.prev:
            self.prev.right = node
            node.left = self.prev
        else:
            # 如果前驱节点为空，说明当前节点是头节点
            self.head = node
        
        # 更新前驱节点
        self.prev = node
        
        # 递归右子树
        self.inorder(node.right)

迭代方法

迭代方法使用栈来模拟递归过程，实现中序遍历。

class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root:
            return None
        
        stack = []
        prev = None
        head = None
        curr = root
        
        while stack or curr:
            # 将左子树全部入栈
            while curr:
                stack.append(curr)
                curr = curr.left
            
            # 弹出栈顶节点
            curr = stack.pop()
            
            # 处理当前节点
            if prev:
                prev.right = curr
                curr.left = prev
            else:
                # 如果前驱节点为空，说明当前节点是头节点
                head = curr
            
            # 更新前驱节点
            prev = curr
            
            # 处理右子树
            curr = curr.right
        
        # 连接头尾节点形成循环链表
        head.left = prev
        prev.right = head
        
        return head

复杂度分析

时间复杂度

无论是递归方法还是迭代方法，我们都需要遍历二叉搜索树中的所有节点。因此，时间复杂度为O(n)，其中n是二叉搜索树中的节点数。

空间复杂度

• 递归方法：递归调用栈的深度取决于树的高度。在最坏情况下（树退化为链表），空间复杂度为O(n)。在平衡二叉树的情况下，空间复杂度为O(log n)。
• 迭代方法：使用栈来模拟递归过程，空间复杂度与递归方法相同。

总结

通过中序遍历二叉搜索树，我们可以在O(n)的时间复杂度内将其转换为有序的双向链表。递归方法和迭代方法各有优缺点，具体选择哪种方法可以根据实际情况和编程习惯来决定。

在实际应用中，这种转换操作可以用于需要将树结构转换为线性结构的场景，例如在某些图形界面中展示树形数据时，可能需要将其转换为链表以便于显示和操作。

希望本文对你理解如何在LeetCode上实现二叉搜索树与双向链表的转换有所帮助。如果你有任何问题或建议，欢迎在评论区留言讨论。