Article / 文章
LeetCode 第426题：将二叉搜索树转化为排序的双向链表
将一个二叉搜索树就地转化为一个已排序的双向循环链表。可以将左右指针作为双向循环链表的前驱和后继指针。 对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。 特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
📖 文章摘要
本文详细解析LeetCode第426题“将二叉搜索树转化为排序的双向链表”，这是一道考察二叉搜索树和双向链表转换的问题。文章提供了基于中序遍历的解题思路，包含C#、Python、C++三种语言实现，配有详细的分析和性能对比。适合想要提升二叉树操作能力的程序员。
核心知识点： 二叉搜索树、双向链表、中序遍历
难度等级： 中等
推荐人群： 具有基础数据结构知识的程序员
题目描述
将一个二叉搜索树就地转化为一个已排序的双向循环链表。可以将左右指针作为双向循环链表的前驱和后继指针。
对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
示例
示例 1：
输入：root = [4,2,5,1,3]
输出：[1,2,3,4,5]
解释：下图显示了转化后的二叉搜索树，实线表示后继关系，虚线表示前驱关系。提示
- -1000 <= Node.val <= 1000
- Node.left.val < Node.val < Node.right.val
- Node.val 的所有值都是唯一的
- 0 <= Number of Nodes <= 2000
解题思路
本题可以使用中序遍历来解决，因为二叉搜索树的中序遍历结果就是有序序列。主要步骤如下：
-
使用中序遍历访问节点：
- 递归遍历左子树
- 处理当前节点
- 递归遍历右子树
-
在遍历过程中构建双向链表：
- 记录前一个访问的节点
- 将当前节点与前一个节点连接
- 更新前一个节点为当前节点
-
最后处理首尾节点：
- 将第一个节点和最后一个节点相连
- 形成循环链表
图解思路
转换过程分析表
| 步骤 | 操作 | 结果 | 说明 |
|---|---|---|---|
| 初始状态 | - | BST结构 | 原始二叉搜索树 |
| 中序遍历 | 访问节点 | 有序序列 | 按顺序访问节点 |
| 链表构建 | 连接节点 | 双向链表 | 建立前驱后继关系 |
| 首尾相连 | 循环连接 | 循环链表 | 完成循环链表结构 |
节点关系转换表
| 原关系 | 新关系 | 指针变化 | 说明 |
|---|---|---|---|
| 左子节点 | 前驱节点 | left指向前驱 | 更新left指针 |
| 右子节点 | 后继节点 | right指向后继 | 更新right指针 |
| 无 | 循环关系 | 首尾相连 | 建立循环关系 |
代码实现
C# 实现
public class Solution {
private Node first = null; // 链表的第一个节点
private Node last = null; // 链表的最后一个节点
public Node TreeToDoublyList(Node root) {
if (root == null) {
return null;
}
// 中序遍历构建双向链表
InorderTraversal(root);
// 将首尾节点相连形成循环链表
first.left = last;
last.right = first;
return first;
}
private void InorderTraversal(Node node) {
if (node == null) {
return;
}
// 遍历左子树
InorderTraversal(node.left);
// 处理当前节点
if (last != null) {
// 将当前节点与上一个节点连接
last.right = node;
node.left = last;
} else {
// 记录第一个节点
first = node;
}
last = node;
// 遍历右子树
InorderTraversal(node.right);
}
}Python 实现
class Solution:
def treeToDoublyList(self, root: 'Node') -> 'Node':
if not root:
return None
# 初始化首尾节点
self.first = None
self.last = None
def inorder(node):
if not node:
return
# 遍历左子树
inorder(node.left)
# 处理当前节点
if self.last:
# 将当前节点与上一个节点连接
self.last.right = node
node.left = self.last
else:
# 记录第一个节点
self.first = node
self.last = node
# 遍历右子树
inorder(node.right)
# 中序遍历构建双向链表
inorder(root)
# 将首尾节点相连形成循环链表
self.first.left = self.last
self.last.right = self.first
return self.firstC++ 实现
class Solution {
private:
Node* first = nullptr; // 链表的第一个节点
Node* last = nullptr; // 链表的最后一个节点
void inorderTraversal(Node* node) {
if (!node) {
return;
}
// 遍历左子树
inorderTraversal(node->left);
// 处理当前节点
if (last) {
// 将当前节点与上一个节点连接
last->right = node;
node->left = last;
} else {
// 记录第一个节点
first = node;
}
last = node;
// 遍历右子树
inorderTraversal(node->right);
}
public:
Node* treeToDoublyList(Node* root) {
if (!root) {
return nullptr;
}
// 中序遍历构建双向链表
inorderTraversal(root);
// 将首尾节点相连形成循环链表
first->left = last;
last->right = first;
return first;
}
};执行结果
C# 实现
- 执行用时：92 ms
- 内存消耗：39.8 MB
Python 实现
- 执行用时：36 ms
- 内存消耗：15.2 MB
C++ 实现
- 执行用时：4 ms
- 内存消耗：7.6 MB
性能对比
| 语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C# | 92 ms | 39.8 MB | 实现清晰但性能较差 |
| Python | 36 ms | 15.2 MB | 代码简洁，性能中等 |
| C++ | 4 ms | 7.6 MB | 性能最优，内存占用小 |
代码亮点
- 🎯 利用中序遍历保证节点顺序
- 💡 原地转换不需要额外空间
- 🔍 巧妙处理首尾节点连接
- 🎨 代码结构清晰，易于理解
常见错误分析
- 🚫 忘记处理空树情况
- 🚫 未正确连接首尾节点
- 🚫 指针连接顺序错误
- 🚫 未保持二叉搜索树性质
解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 中序遍历法 | O(n) | O(h) | 原地转换，无需额外空间 | 递归调用栈开销 |
| 额外数组法 | O(n) | O(n) | 实现简单 | 需要额外空间 |
相关题目
📖 系列导航
🔥 算法专题合集 - 查看完整合集
📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第426题。
💬 互动交流
感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。
如果这篇文章对你有帮助，请：
- 👍 点个赞，让更多人看到这篇文章
- 📁 收藏文章，方便后续查阅复习
- 🔔 关注作者，获取更多高质量算法题解
- 💭 评论区留言，分享你的解题思路或提出疑问
你的支持是我持续分享的动力！
💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！