剑指 Offer 二叉搜索树与双向链表

问题描述

在面试过程中，经常会遇到关于数据结构转换的问题。本篇文章将探讨如何将一个给定的二叉搜索树（BST）转化为一个双向链表。具体来说，你需要保留原树中的节点顺序，并且每个节点的左右指针分别指向其前驱和后继。

二叉搜索树与双向链表

在开始解决问题之前，我们先了解一下二叉搜索树和双向链表的基本概念。

• 二叉搜索树：一个有序的二叉树。对于树中的任意一个节点，其左子树的所有节点值小于该节点的值，右子树的所有节点值大于该节点的值。
• 双向链表：每个节点有两个指针，分别指向前驱和后继节点。

解题思路

我们的目标是将二叉搜索树转化为双向链表。为了达成这个目标，可以采用中序遍历的方式来实现，因为中序遍历能够保证元素的有序性，符合双向链表的要求。

具体步骤如下：

1. 定义节点结构：首先定义一个节点结构体 TreeNode。
2. 初始化指针：使用两个指针来记录转换后的链表头尾节点。
3. 中序遍历：采用递归或者迭代的方式进行中序遍历，调整每个节点的左右指针。
4. 返回结果：最后返回转换后的双向链表头节点。

代码实现

以下是使用 Python 实现上述思路的一个示例：

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

def treeToDoublyList(root: TreeNode) -> TreeNode:
    if not root:
        return None
    
    # 中序遍历的辅助函数
    def inorder(node, pre_node):
        nonlocal head, tail
        if node is None:
            return
        
        inorder(node.left, pre_node)
        
        # 处理当前节点
        if pre_node:
            pre_node.right = node
            node.left = pre_node
        else:
            # 第一个节点
            head = node
        
        tail = node  # 更新尾节点
        
        inorder(node.right, node)
    
    head, tail = None, None
    inorder(root, None)
    
    # 将双向链表首尾相连
    if head and tail:
        head.left = tail
        tail.right = head
    
    return head

解析

1. 节点结构体：定义了 TreeNode 结构，包含值、左子节点和右子节点。
2. 中序遍历函数：通过递归方式实现中序遍历，并在每个节点处理时更新指针。
3. 头尾节点记录：使用全局变量 head 和 tail 来记录链表的首尾节点。
4. 返回结果：最后将双向链表的头尾节点相连，确保形成一个闭合循环。

通过上述方法，我们可以有效地将二叉搜索树转化为双向链表。这种转换不仅保留了原树中的元素顺序，还使得每个节点都能指向其前驱和后继节点，非常适合用于后续的一些数据操作或查询任务。