26 二叉搜索树与双向链表

题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

示例：

原树:
    10
   /  \
  5    12
 / \
4   7

转换后的双向链表:
4 <-> 5 <-> 7 <-> 10 <-> 12

解题思路

核心思想：二叉搜索树的中序遍历结果是有序的，利用中序遍历调整指针。

关键步骤：

1. 中序遍历二叉搜索树
2. 遍历过程中，将当前节点的left指向前驱，right指向后继
3. 记录前驱节点和链表头节点

时间复杂度：O(n) 空间复杂度：O(n)

Python 实现

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


def convert_bst_to_linked_list(root):
    """
    将二叉搜索树转换为排序双向链表

    Args:
        root: 二叉搜索树根节点

    Returns:
        TreeNode: 双向链表的头节点
    """
    if not root:
        return None

    # 中序遍历
    def inorder(node):
        nonlocal prev, head

        if not node:
            return

        # 递归处理左子树
        inorder(node.left)

        # 处理当前节点
        if prev:
            prev.right = node
            node.left = prev
        else:
            head = node  # 最左边的节点是头节点

        prev = node

        # 递归处理右子树
        inorder(node.right)

    prev = None
    head = None
    inorder(root)

    return head


# 辅助函数：打印双向链表
def print_doubly_linked_list(head):
    if not head:
        print("Empty")
        return

    result = []
    curr = head
    while curr:
        result.append(str(curr.val))
        curr = curr.right
    print(' <-> '.join(result))


# 测试代码
if __name__ == "__main__":
    # 创建二叉搜索树:
    #     10
    #    /  \
    #   5    12
    #  / \
    # 4   7
    root = TreeNode(10)
    root.left = TreeNode(5)
    root.right = TreeNode(12)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(7)

    head = convert_bst_to_linked_list(root)
    print("双向链表:")
    print_doubly_linked_list(head)
    # 输出: 4 <-> 5 <-> 7 <-> 10 <-> 12

图解

中序遍历顺序: 4, 5, 7, 10, 12

转换过程:

原树:
    10
   /  \
  5    12
 / \
4   7

中序遍历:
访问4: prev=None, head=4, prev=4
访问5: 4.right=5, 5.left=4, prev=5
访问7: 5.right=7, 7.left=5, prev=7
访问10: 7.right=10, 10.left=7, prev=10
访问12: 10.right=12, 12.left=10, prev=12

最终链表:
4 <-> 5 <-> 7 <-> 10 <-> 12