LeetCode 426. 将二叉搜索树转化为排序的双向链表
目录
题目描述
题意分析
给一棵二叉搜索树，要求把它改造成一个按值升序排列的循环双向链表，并返回指向最小元素的指针。节点类型不变，
left被复用为链表的前驱指针，right被复用为后继指针。有三个约束必须同时满足，缺一不可。第一是升序，这决定了访问节点的顺序必须与二叉搜索树的有序性对齐。第二是原地，题目明确要求就地转换，不允许新建节点，也就不能先把值收集到数组再重新建链——那样虽然思路更直白，却违背题意，面试中会被判为没读懂题。第三是循环，最小节点的前驱要指向最大节点，最大节点的后继要指向最小节点，这一步发生在遍历之外，很容易漏掉。
边界情况有三种：空树必须返回空，而不是去访问某个不存在的头节点；单节点树的结果是一个自环，它的前驱和后继都指向自己；退化成一条链的树（例如所有节点只有右孩子）也要能正确处理，此时链表顺序与树的形状完全一致。
解法：中序遍历原地双向连接
核心思路
二叉搜索树的中序遍历天然按升序访问节点。访问当前节点时，它的链表前驱就是上一个访问的节点
pre，因此直接连接pre.right = node和node.left = pre，不需要先把节点收集到数组中。第一个访问的节点是最小值，记为
head；遍历结束时pre是最大值。最后连接head.left = pre、pre.right = head，把普通双向链表闭成环。不变量：访问当前节点前，
head到pre已是包含全部已访问节点的升序双向链表。中序位置只改写当前节点的left和前驱的right，当前节点原来的右子树仍可继续递归。
解题步骤
- 空树直接返回空；初始化共享变量
head、pre。- 递归遍历左子树。
- 访问当前节点：
pre为空时记录head，否则双向连接pre与当前节点。- 更新
pre = node，再遍历右子树。- 遍历完成后连接头尾，返回最小节点
head。例如
[4,2,5,1,3]的中序序列是1,2,3,4,5。遍历时依次连接相邻节点，最后再连接 $1$ 与 $5$，即可得到循环双向链表。
代码实现
class Solution {
private Node head;
private Node pre;
public Node treeToDoublyList(Node root) {
head = null;
pre = null;
if (root == null) {
return null;
}
dfs(root);
head.left = pre;
pre.right = head;
return head;
}
private void dfs(Node node) {
if (node == null) {
return;
}
dfs(node.left);
if (pre == null) {
head = node;
} else {
pre.right = node;
node.left = pre;
}
pre = node;
dfs(node.right);
}
}
func treeToDoublyList(root *Node) *Node {
if root == nil {
return nil
}
var head *Node
var pre *Node
var dfs func(*Node)
dfs = func(node *Node) {
if node == nil {
return
}
dfs(node.Left)
if pre == nil {
head = node
} else {
pre.Right = node
node.Left = pre
}
pre = node
dfs(node.Right)
}
dfs(root)
head.Left = pre
pre.Right = head
return head
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点恰好访问并连接一次。
- 空间复杂度：$O(h)$，$h$ 为树高，开销来自递归栈；平衡树为 $O(\log n)$，退化树为 $O(n)$。
关键点总结
- BST 的中序顺序就是目标链表顺序；
pre把遍历顺序转成相邻关系。- 每次连接必须同时设置前驱的
right与当前节点的left。- 头尾闭环只能在遍历结束后完成，否则会破坏尚未遍历的树结构。
- Java 使用成员变量保存状态时，入口必须重置，避免同一
Solution实例多次调用时串链。
易错点总结
- 忘记处理空树：遍历后访问
head.left会触发空指针异常。- 只连接一个方向：正向遍历可能正常，反向链却仍是原树指针。
- 忘记连接
head与pre：得到的是普通双向链表，不是循环链表。- 使用先序或后序访问点连接：节点顺序不再保证升序。
- 成员变量不重置：多次调用会把新树接到旧链表上。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 98. 验证二叉搜索树 | 中等 | 用 pre 校验中序序列是否严格递增，不修改指针 |
| 230. 二叉搜索树中第 K 小的元素 | 中等 | 中序计数到第 $k$ 个即可提前终止，重点在剪枝 |
| 538. 把二叉搜索树转换为累加树 | 中等 | 反序中序（右根左）累加前缀和，修改的是值不是结构 |
| 897. 递增顺序搜索树 | 简单 | 转成只有右孩子的单向链，需把 left 显式置空 |
| 1038. 从二叉搜索树到更大和树 | 中等 | 与 538 同解，考察反序遍历时累加变量的共享 |
| LCR 052. 递增顺序搜索树 | 简单 | 与 897 同题，可对比新建节点与原地改指针两种写法 |
| LCR 054. 把二叉搜索树转换为累加树 | 中等 | 与 538 同题，适合练习迭代版反序中序 |
| 剑指 Offer 36. 二叉搜索树与双向链表 | 中等 | 与本题同题，同样要求返回循环双向链表 |
| 剑指 Offer 54. 二叉搜索树的第k大节点 | 简单 | 求第 $k$ 大，需把中序方向反过来走 |
| 面试题 04.05. 合法二叉搜索树 | 中等 | 与 98 同题，注意重复值与极值边界的处理 |
| 面试题 17.12. BiNode | 简单 | 转单向链表且不闭环，是本题去掉双向与循环的简化版 |