目录
基本要求
节点结构
核心算法：中序遍历 + 指针修改
算法思想
递归实现
非递归实现
复杂度分析
时间复杂度：
空间复杂度：
基本要求
这是一个经典的算法问题：将二叉搜索树（BST）转换成一个排序的双向循环链表（或双向链表）。
通常题目要求是：
- 双向链表中的节点顺序与二叉搜索树的中序遍历顺序一致（即升序）。
- 需要将节点的左右指针分别作为双向链表的前驱（prev）和后继（next）指针。
- 有时要求链表是循环的（头尾相连），有时只要求是双向链表。
- 原地转换：不能创建新节点，只能调整原有指针
节点结构
class Node { public: int val; Node* left; Node* right; Node(int _val) : val(_val), left(nullptr), right(nullptr) {} };核心算法：中序遍历 + 指针修改
算法思想
利用BST(二叉搜索树)的中序遍历特性：
- 中序遍历BST会按升序访问所有节点
- 在遍历过程中，记录前一个访问的节点（prev）
- 将当前节点与prev节点双向连接
- 遍历完成后，连接头尾节点形成循环
递归实现
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)
