力扣刷题TOP101: 24.BM30 二叉搜索树与双向链表

目录：

目的

思路

复杂度

记忆秘诀

python代码

目的：

将二叉搜索树转换成一个排序的双向链表。

思路

这个任务是一棵 二叉搜索树（BST） 转换成一个 双向链表，并且要求不能添加新的节点，只能在原有的节点基础上调整指针，且返回链表中第一个节点的指针。我们可以利用 中序遍历 来实现这个转换，因为中序遍历二叉搜索树时，节点是按递增顺序访问的。

中序遍历过程可参考：
力扣刷题TOP101：20-22.BM23-25 二叉树的前中后序遍历-CSDN博客

假设我们有一个网站要测试，结构如下：

               首页（4） 
        /                   \
   技术文档（2）           联系我们（6）
    /     \                  /
用户指南（1）用户帮助（3） 公司团队（5）

每个页面（节点）都有两个按钮（指针）：

• 左指针left（返回按钮）：指向上一个页面。
• 右指针right（下一页按钮）：指向下一个页面。

准备测试网站：

当测试开始时，首先准备两个关键变量：

• self.last: 这个变量用来记录上一个访问过的页面。它在递归过程中不断更新，以便在每次访问到一个页面时，能将它与前一个页面相互连接。
• self.head: 这个变量用来记录链表的第一个节点，即网站的首页。首页是最左端的页面，所有页面的导航链条都从这里开始。

开始测试页面：

• 递归左侧页面：这个过程就像用户点击进入网站时，从首页开始，递归地访问每个子页面。inorder(node.left)
• 处理当前页面：每访问一个页面（节点），程序员就检查self.last（前一个页面）是否存在。如果存在，程序员会：
  • 将前一个页面的right指针指向当前页面。self.last.right = node
  • 将当前页面的left指针指向前一个页面。node.left = self.last
  • 如果当前页面是第一个访问的页面（self.last 是 None），那么就将它设置为链表的头节点（即用户的首页）。self.head = node
  • 测试没问题，记录当前页面。self.last = node

• 递归右侧页面： 访问完左子页面和当前页面后，程序员会递归访问右侧页面。inorder(node.right)

• 返回链表头节点： 完成递归遍历后，程序员将返回首页即链表的头节点return self.head
  • 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6

复杂度

• 时间复杂度：O(n）

  • 对每个节点只进行了访问一次，其中 n 是树中的节点数。

• 空间复杂度：O(1)

  • 我们只用了常量空间来存储指针。

记忆秘诀

• 中序遍历：通过中序遍历，能够按顺序访问到二叉搜索树的节点。
• 连接指针：在遍历的过程中，使用两个指针（last 和 head）来维护链表的前驱和头指针。
• 前驱后继：将每个节点的 left 指针指向前驱，right 指针指向后继。

python代码

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

class Solution:
    def Convert(self, pRootOfTree: TreeNode) -> TreeNode:
        if not pRootOfTree:
            return None
        
        self.last = None  # 用来记录前一个页面
        self.head = None  # 用来记录第一个页面

        def inorder(node):
            if not node:
                return
            
            # 遍历左子页面
            inorder(node.left)
            
            # 当前页面与前一个页面建立链接
            if self.last:
                self.last.right = node  # 前一个页面的"下一页"指向当前页面
                node.left = self.last    # 当前页面的"返回"指向前一个页面
            else:
                self.head = node  # 第一个页面，设置为链表的头节点

            self.last = node  # 更新"前一个页面"为当前页面
            
            # 遍历右子页面
            inorder(node.right)
        
        inorder(pRootOfTree)  # 开始中序遍历
        return self.head  # 返回链表的第一个页面

* 欢迎大家探讨新思路，能够更好的理解和记忆