LeetCode 补充题 195. 二叉搜索树转非循环双向链表
题目描述
[!green]
牛客原题： ✅ 补充题 195. 二叉搜索树转非循环双向链表
给定二叉搜索树
root，原地转换为按节点值递增的普通双向链表。
left指向前驱，right指向后继；头的前驱和尾的后继均为空，返回头节点。
示例 1：
输入：
root = [2,1,3]
输出：1 <-> 2 <-> 3
解释： 头节点left和尾节点right均为空。
提示：
- 允许空树。
- 节点值互不相同。
- 只能调整原节点指针，不能创建新的链表节点。
- 牛客原题要求 O(n) 时间、O(1) 额外空间；补充解法满足这一空间要求。
题意分析
二叉搜索树的中序顺序已经符合链表排序要求，核心是把访问顺序转换成前驱、后继指针。节点本身可以复用，但仍须区分递归栈开销和常数空间方案；结果是一条首尾为空的普通双向链表。
解法：中序连接
核心思路
[!blue]
二叉搜索树中序遍历得到升序节点流。
pre保存已经输出的尾节点，head保存第一个输出节点；访问当前节点时，让pre.right指向当前节点、当前节点的left指回 pre，再推进尾指针。第一次访问没有前驱，只记录 head。中序遍历完成后，头的 left 和尾的 right 都置空，形成普通双向链表；不能再把首尾连接成环。
递归栈负责保留尚未访问的祖先，因此这版容易按“左、根、右”现场写出，但辅助空间是树高
O(h)，不能因为节点复用就宣称额外空间为常数。
解题步骤
- 重置 head 和 pre，再递归访问根节点的左子树。
- 访问当前节点时，若 pre 为空则记录链表头，否则连接 pre.right 与当前节点。
- 将当前节点的 left 指向 pre，更新 pre 后继续访问右子树。
- 遍历完成后将头的 left、尾的 right 置空，返回 head。
代码实现
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 = null;
pre.right = null;
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 = nil
pre.Right = nil
return head
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：递归栈空间 $O(h)$，$h$ 为树高。
关键点总结
[!green]
中序遍历时连接前驱和当前节点，最终将首尾边界显式置空，不再闭合成环。
补充解法：右旋展开为常数空间双向链表
核心思路
[!blue]
牛客原题要求额外空间为常数。递归版虽然复用了原节点，仍有调用栈；可以改用右旋，把尚未处理的树逐步展开成只有右孩子的有序链。
cur指向待处理部分的根，pre指向已经排好序的链表尾部。若cur有左孩子left，让left上升：先将left.right接到cur.left，再令left.right = cur。右旋保持中序顺序不变，并让一个更小的节点来到当前入口。已有前缀时将pre.right接到新入口，否则更新head，然后继续检查上升后的节点。当
cur.left为空时，当前节点就是剩余部分中的最小节点，可以正式接入链表。令cur.left = pre建立前驱，再将pre推进到当前节点、cur推进到右孩子。已完成部分只通过right向后连接，不再参与旋转。所有节点依次接入后，右指针已经构成升序链，左指针也逐个连向前驱。第一个节点的前驱自然为空，最后一个节点的后继自然为空，整条链不会首尾相接。整个过程只修改原节点的指针，不创建新节点。
解题步骤
- 令
head、cur指向原根，pre为空。- 当前节点有左孩子时，右旋一次并更新待处理部分的入口。
- 当前节点无左孩子时，把它接入有序前缀，并沿右指针继续处理。
- 当前节点为空时返回
head。
代码实现
class Solution {
public Node treeToDoublyList(Node root) {
Node head = root;
Node pre = null;
Node cur = root;
while (cur != null) {
if (cur.left != null) {
Node left = cur.left;
cur.left = left.right;
left.right = cur;
if (pre == null) {
head = left;
} else {
pre.right = left;
}
cur = left;
} else {
cur.left = pre;
pre = cur;
cur = cur.right;
}
}
return head;
}
}
func treeToDoublyList(root *Node) *Node {
head, cur := root, root
var pre *Node
for cur != nil {
if cur.Left != nil {
left := cur.Left
cur.Left = left.Right
left.Right = cur
if pre == nil {
head = left
} else {
pre.Right = left
}
cur = left
} else {
cur.Left = pre
pre = cur
cur = cur.Right
}
}
return head
}
复杂度分析
- 时间复杂度：$O(n)$。每个节点正式接入一次；每次右旋会让从头沿右指针能访问到的节点数增加一个，右旋总次数不超过 $n-1$。
- 空间复杂度：$O(1)$，只使用固定数量的节点引用，没有递归栈、显式栈或新节点。
关键点总结
[!green]
- 右旋保持中序顺序，左孩子的原右子树需要先接回，不能丢失。
- 只有当前节点没有待处理左子树时，才能把左指针改成链表前驱。
- 修改待处理部分入口后，要同步连接已完成的前缀尾部或更新头节点。
- 原树结构会被转换成普通双向链表，首尾指针保持为空。
易错点总结
[!yellow]
- 同一个求解对象可能被重复调用，每次先重置 head 和 pre。
- 递归遍历完左子树后再改写当前节点的 left，避免破坏尚未访问的结构。
- 头尾保持为空，不能套用循环双向链表的收尾逻辑。
- 递归版仍占用树高级别的栈空间；要求常数空间时使用后面的右旋方案。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 426. 将二叉搜索树转化为排序的双向链表 | 中等 | 都按中序顺序连接前驱与后继；该题最终将首尾相连成环，本题必须令头的前驱和尾的后继为空。 |