# 426. 将二叉搜索树转化为排序的双向链表
**难度**：中等
**相关标签**：树、二叉搜索树、双向链表、中序遍历、递归
## 📌 题目描述（中文）
将一个二叉搜索树（BST）转换为一个排序的循环双向链表。要求不能创建任何新的节点，只能通过调整树中节点的指针来实现。
转换规则：
- 树中每个节点的 `left` 指针调整为指向前驱节点（双向链表中的 `prev`）
- 树中每个节点的 `right` 指针调整为指向后继节点（双向链表中的 `next`）
- 最终返回链表中的第一个节点（即最小的节点）
- 链表必须是循环的：第一个节点的 `left` 指向最后一个节点，最后一个节点的 `right` 指向第一个节点
必须通过**中序遍历**访问节点，仅调整原节点指针，不新建节点。
## 代码框架
```java
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
public Node treeToDoublyList(Node root) {
// 请在这里实现你的代码
}
}
```
## 📥 输入与 📤 输出
- **输入**：二叉搜索树（BST）的根节点 `root`（可能为空）
- **输出**：转换后的循环双向链表的头节点（即最小值节点）
## 🧪 示例 1
**输入树结构**：
```
4
/ \
2 5
/ \
1 3
```
**中序遍历结果**：1 → 2 → 3 → 4 → 5
**转换后链表**：1 ↔ 2 ↔ 3 ↔ 4 ↔ 5（循环结构）
- 节点 1 的 `left` 指向节点 5
- 节点 5 的 `right` 指向节点 1
**输出**：节点 1（最小值节点）
## ⚠️ 约束条件
- 树中节点数量范围：[0, 2000]
- 节点值范围：-1000 ≤ Node.val ≤ 1000
- BST 特性：Node.left.val < Node.val < Node.right.val（无重复值）
解答如下
```java
Node pre = null;
Node head = null;
public Node treeToDoublyList(Node root) {
this.pre = null;
this.head = null;
if (root == null) {
return root;
}
dfs(root);
// 连接头尾，形成循环链表
// 此时 pre 是最后一个节点（即最大值节点）
head.left = pre;
pre.right = head;
return head;
}
private void dfs(Node node) {
if (node == null) {
return;
}
dfs(node.left);
// 处理当前节点
if (pre == null) {
// 如果 pre 为空，说明这是中序遍历的第一个节点（最小值节点）
head = node; // 记录头节点
} else {
// 否则，将前一个节点的 right 指向当前节点，当前节点的 left 指向前一个节点
pre.right = node;
node.left = pre;
}
// 更新 pre 为当前节点
pre = node;
dfs(node.right);
}
```