如何把二叉搜索树转换成一个有序的双向链表？

简化版

因为 BST 中序遍历得升序，转有序双向链表的本质就是：做一次中序遍历，把访问到的节点按顺序用指针串起来——把每个节点的 left 当作前驱指针、right 当作后继指针。用一个 prev 变量记住上一个访问的节点，每访问一个当前节点，就让 prev.right = cur、cur.left = prev。要求原地转换（复用原节点，不新建）。

详细版

TreeNode prev = null, head = null;
TreeNode treeToDoublyList(TreeNode root) {
    if (root == null) return null;
    inorder(root);
    // 首尾相连成循环双向链表（如题目要求循环）
    head.left = prev;
    prev.right = head;
    return head;
}
void inorder(TreeNode cur) {
    if (cur == null) return;
    inorder(cur.left);
    // —— 中序访问当前节点，接到链表尾部 ——
    if (prev == null) head = cur;      // 第一个节点即链表头
    else { prev.right = cur; cur.left = prev; }  // 双向连接
    prev = cur;                         // 更新 prev
    inorder(cur.right);
}

prev 始终指向「已连好链表的最后一个节点」。
每访问一个 cur，把它接到 prev 后面，形成双向指针。
遍历结束后，head 是最小节点、prev 是最大节点，按需首尾相连成循环链表。

完整版教学

一、为什么中序遍历是钥匙

有序双向链表要求节点从小到大排列，而 BST 的中序遍历（左根右）恰好就是从小到大访问节点。所以「转有序链表」= 「按中序顺序把节点连起来」。链表用的两个指针可以直接复用树节点已有的字段：left 当前驱、right 当后继（原地转换，不额外分配内存）。

二、prev 指针的作用

转换过程中我们需要「一边中序遍历，一边把当前节点接到已建好的链表尾巴上」。用一个全局的 prev 记录上一个被中序访问的节点（也就是链表当前的尾节点）。每访问一个新节点 cur：

若 prev == null：说明 cur 是中序第一个（最小值），把它设为链表头 head。
否则：把 cur 接到 prev 后面——prev.right = cur（后继）、cur.left = prev（前驱）。
然后 prev = cur，链表尾巴前移。

这个「用 prev 串联中序序列」的模式，和「BST 转链表」「恢复 BST」「验证 BST」是同一类手法。

三、指针连接的时机

关键是在「中序访问当前节点」的那个位置做连接——也就是递归左子树之后、递归右子树之前。这样才能保证连接顺序严格按升序进行。如果把连接写在前序或后序位置，顺序就乱了。

四、循环还是非循环

非循环双向链表：遍历结束直接返回 head，最后一个节点 prev.right 保持 null。
循环双向链表（常见题目要求）：遍历完后把头尾相连——head.left = prev（头的前驱是尾）、prev.right = head（尾的后继是头）。

按题目要求选择，逻辑主体一样。

五、复杂度与延伸

时间 O(n)：一次中序遍历。
空间 O(h)：递归栈；用 Morris 中序遍历可做到 O(1) 额外空间。
延伸：反过来「有序双向链表 → 平衡 BST」可用「中序自底向上构建」，和「有序数组转 BST」思路一致。这类「BST ↔ 有序结构」的互转都围绕中序展开。

六、常见误区与追问

考点	正确口径
遍历顺序	中序遍历，因为 BST 中序天然升序
核心指针	`prev` 指向已处理链表的尾节点
连接动作	`prev.right = cur` 且 `cur.left = prev`

inorder(cur):
  inorder(cur.left)
  link(prev, cur)
  prev = cur
  inorder(cur.right)

这题的关键不是新建链表，而是在中序遍历过程中原地改左右指针。

误区：需要先把节点值放进数组再建链表。 可以这样做但不是最优；面试更看重中序过程中直接串指针，空间只用递归栈。
误区：只设置 prev.right 就够了。 双向链表还必须设置 cur.left = prev，否则只能单向遍历。
误区：可以先递归右子树再连接当前节点。 BST 升序依赖左根右顺序，连接时机必须在左子树处理完、右子树处理前。
追问：头节点如何确定？ 第一次访问到的节点就是最小节点，也就是链表头；可用 head == null 时记录。
追问：循环双向链表怎么收尾？ 遍历结束后让 head.left = prev、prev.right = head，其中 prev 是尾节点。
追问：空间复杂度是多少？ 递归版 O(h)，h 是树高；若用 Morris 中序可以做到 O(1) 额外空间，但代码复杂。

七、加强记忆

BST 转有序双向链表 = 中序遍历（升序）把节点串起来，复用 left 作前驱、right 作后继（原地）。用全局 prev 记住链表尾，每中序访问一个 cur 就 prev.right=cur; cur.left=prev，连接要写在中序位置（递归左之后、右之前）。第一个节点是 head（最小），结束可将头尾相连成循环链表。O(n) 时间，Morris 可 O(1) 空间。

简化版

详细版