二叉搜索树与双向链表 - JZ26

题目描述

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

转换规则：

左指针指向前驱节点
右指针指向后继节点
头节点的左指针指向尾节点
尾节点的右指针指向头节点

示例：

输入BST:     4
           /   \
          2     5
         / \
        1   3

输出双向循环链表: 1<->2<->3<->4<->5，并且1的左指针指向5，5的右指针指向1

解题思路

这道题结合了BST的中序遍历和双向链表操作：

核心思路：

BST的中序遍历序列是有序的
在中序遍历过程中，调整节点指针
维护前驱节点，建立双向连接
最后连接头尾节点形成循环

具体步骤：

中序遍历BST
对于每个节点，将其左指针指向前驱节点
将前驱节点的右指针指向当前节点
更新前驱节点为当前节点
最后将头尾相连

项目结构

.
├── go.mod              # Go 模块定义
├── types.go            # 二叉树节点定义和工具函数
├── solution.go         # 算法实现（你需要完成这个文件）
├── answer.go           # 参考答案（练习后查看）
├── solution_test.go    # 单元测试
└── README.md          # 说明文档

使用方法

1. 实现算法

在 solution.go 文件中实现：

treeToDoublyList(root *TreeNode) *TreeNode - 主要实现
treeToDoublyListRecursive(root *TreeNode) *TreeNode - 递归版本
treeToDoublyListIterative(root *TreeNode) *TreeNode - 迭代版本

2. 运行测试

go test -v
go test -bench=.

时间和空间复杂度分析

方法	时间复杂度	空间复杂度	说明
递归中序遍历	O(n)	O(n)	递归调用栈
迭代中序遍历	O(n)	O(n)	显式栈
Morris遍历	O(n)	O(1)	不使用额外空间

知识点

二叉搜索树性质
中序遍历
双向链表操作
指针操作
递归与迭代转换

为何使用中序遍历？

原因在于：二叉搜索树的中序遍历天然保证升序顺序，因此为了得到一个有序双向链表，必须用中序遍历。

二叉搜索树有一个重要性质：

对于任意节点：
- 左子树的所有节点值小于当前节点
- 右子树的所有节点值大于当前节点

➡ 如果我们要得到一个 升序序列，自然会联想到 中序遍历。

假设 BST 节点值为 [4, 2, 5, 1, 3]，结构如下：

不同遍历方式的结果：

前序遍历（根 -> 左 -> 右）： 4, 2, 1, 3, 5 （不是有序的）
后序遍历（左 -> 右 -> 根）： 1, 3, 2, 5, 4 （不是有序的）
中序遍历（左 -> 根 -> 右）： 1, 2, 3, 4, 5 （有序！）

所以，要把 BST 转换成有序双向链表，就必须用 中序遍历。

中序遍历规则是：左子树 → 根节点 → 右子树。

一路往左：把当前节点依次入栈，直到最左节点。
处理栈顶：当不能再往左时，弹出栈顶节点，访问它（在这里就是“把它接到双向链表”）。
转向右子树：处理完栈顶后，转向它的右子树，继续步骤 1。

如此循环，直到栈为空且当前节点也为空。

对应的代码：

for current != nil || len(stack) > 0 {
    // 1. 一直往左，把沿途节点压栈
    for current != nil {
        stack = append(stack, current)
        current = current.Left
    }

    // 2. 没有更左了 -> 处理栈顶节点
    current = stack[len(stack)-1]
    stack = stack[:len(stack)-1] // 出栈

    // 这里就是“访问节点”的位置 (中序遍历的核心时刻)
    // 在本题中，不仅访问，还要 “链接 prev <-> current”

    // 3. 转向右子树
    current = current.Right
}

迭代实现算法步骤详解

1. 初始化阶段

stack := make([]*TreeNode, 0)  // 用于中序遍历的栈
current := root                // 当前处理的节点
var prev, head *TreeNode       // prev: 上一个处理的节点, head: 链表头节点

2. 中序遍历过程

for current != nil || len(stack) > 0 {
    // 步骤1: 找到最左节点
    for current != nil {
        stack = append(stack, current)
        current = current.Left
    }
    
    // 步骤2: 处理栈顶节点
    current = stack[len(stack)-1]
    stack = stack[:len(stack)-1]
    
    // 步骤3: 连接节点
    if prev != nil {
        prev.Right = current    // 前一个节点的右指针指向当前节点
        current.Left = prev     // 当前节点的左指针指向前一个节点
    } else {
        head = current          // 第一个节点作为头节点
    }
    prev = current
    
    // 步骤4: 处理右子树
    current = current.Right
}

3. 形成循环

if head != nil && prev != nil {
    head.Left = prev    // 头节点的左指针指向尾节点
    prev.Right = head   // 尾节点的右指针指向头节点
}

举例说明

假设有如下二叉搜索树：

执行过程：

中序遍历顺序: 1 → 2 → 3 → 4 → 5
连接过程:
- 处理节点1: head = 1, prev = 1
- 处理节点2: 1 ↔ 2, prev = 2
- 处理节点3: 2 ↔ 3, prev = 3
- 处理节点4: 3 ↔ 4, prev = 4
- 处理节点5: 4 ↔ 5, prev = 5
形成循环: 1 ↔ 5 (首尾相连)

最终结果:

1 ↔ 2 ↔ 3 ↔ 4 ↔ 5
↑_______________↓

算法特点

时间复杂度: O(n) - 每个节点访问一次
空间复杂度: O(h) - h为树的高度，用于栈空间
核心思想: 利用中序遍历的迭代实现，在遍历过程中逐步建立双向链接关系
关键操作: 维护 prev 指针来连接相邻节点，最后连接首尾形成循环

这是一个经典的树结构转换问题的优雅解决方案。

题目描述​

解题思路​

项目结构​

使用方法​

1. 实现算法​

2. 运行测试​

时间和空间复杂度分析​

知识点​

为何使用中序遍历？​

迭代实现算法步骤详解​

1. 初始化阶段​

2. 中序遍历过程​

3. 形成循环​

举例说明​

算法特点​