二叉搜索树与双向链表

目录

基本要求

节点结构

核心算法：中序遍历 + 指针修改

算法思想

递归实现

非递归实现

复杂度分析

时间复杂度：

空间复杂度：

基本要求

这是一个经典的算法问题：将二叉搜索树（BST）转换成一个排序的双向循环链表（或双向链表）。

通常题目要求是：

1. 双向链表中的节点顺序与二叉搜索树的中序遍历顺序一致（即升序）。
2. 需要将节点的左右指针分别作为双向链表的前驱（prev）和后继（next）指针。
3. 有时要求链表是循环的（头尾相连），有时只要求是双向链表。
4. 原地转换：不能创建新节点，只能调整原有指针

节点结构

class Node { public: int val; Node* left; Node* right; Node(int _val) : val(_val), left(nullptr), right(nullptr) {} };

核心算法：中序遍历 + 指针修改

算法思想

利用BST(二叉搜索树)的中序遍历特性：

1. 中序遍历BST会按升序访问所有节点
2. 在遍历过程中，记录前一个访问的节点（prev）
3. 将当前节点与prev节点双向连接
4. 遍历完成后，连接头尾节点形成循环

递归实现

class Solution { private: Node* prev = nullptr; // 记录前驱节点 Node* head = nullptr; // 记录链表头节点 // 中序遍历递归函数 void inorderTraversal(Node* curr) { if (!curr) return; // 1. 递归遍历左子树 inorderTraversal(curr->left); // 2. 处理当前节点 if (!prev) { // 第一个节点（最小值），设为头节点 head = curr; } else { // 连接前驱和当前节点 prev->right = curr; curr->left = prev; } // 更新prev为当前节点 prev = curr; // 3. 递归遍历右子树 inorderTraversal(curr->right); } public: Node* treeToDoublyList(Node* root) { if (!root) return nullptr; // 中序遍历并调整指针 inorderTraversal(root); //如果需要转换BST为双向循环链表（不需要删除下面两行代码即可） // 连接头尾形成循环链表 head->left = prev; // 头的前驱指向尾 prev->right = head; // 尾的后继指向头 return head; } };

非递归实现

不使用递归，通过显式栈来模拟中序遍历的过程，在遍历过程中调整指针指向。

class Solution { public: Node* treeToDoublyList(Node* root) { if (!root) return nullptr; Node* prev = nullptr; Node* head = nullptr; stack<Node*> st; Node* curr = root; // 中序遍历（迭代版） while (curr || !st.empty()) { // 左子树入栈 while (curr) { st.push(curr); curr = curr->left; } // 弹出当前节点 curr = st.top(); st.pop(); // 连接节点 if (!prev) { head = curr; // 第一个节点 } else { prev->right = curr; curr->left = prev; } prev = curr; curr = curr->right; // 处理右子树 } //如果需要转换BST为双向循环链表（不需要删除下面两行代码即可） // 形成循环 head->left = prev; prev->right = head; return head; } };

复杂度分析

时间复杂度：

O(n)：每个节点被访问一次，n为节点总数

空间复杂度：

O(h)，h为树的高度

• 最坏情况（链状树）：O(n)
• 最好情况（平衡树）：O(log n)