LeetCode 剑指 Offer 36. 二叉搜索树与双向链表
目录
题目描述
题意分析
输入一棵二叉搜索树，要求把它变成一条「排序的循环双向链表」，并返回链表中最小元素对应的那个节点。
题目给的节点结构里只有
left和right两个指针，转换后left当作前驱、right当作后继。题面明确了两个硬性要求，它们决定了这题只能怎么做：
- 不能新建节点：不允许先中序遍历收集到一个数组、再另建链表，只能在原树的节点上就地改写
left与right。这等于说「遍历」和「建链」必须同时发生。- 必须是循环链表：不仅相邻节点要互指，最小节点的
left要指向最大节点，最大节点的right要指向最小节点，首尾也得闭合。很多人写完中间部分就交卷，恰恰漏掉这一步。约束信号：给的是「二叉搜索树」而不是普通二叉树，说明有序性是题目送的礼物，不需要自己排序；要求「排序的」链表，说明输出顺序是唯一确定的，可以拿来当正确性校验。
边界：空树要直接返回空，此时既没有头也没有尾，任何「首尾相连」的写法都会踩空；单节点树也要成环，它的
left和right都指向自己。
解法：迭代中序原地串联
核心思路
问题关键：二叉搜索树的中序遍历天然按升序访问节点，恰好就是目标链表的顺序。题目又要求复用原节点，因此可以在中序访问到当前节点时，直接把它与上一个访问节点连成双向链表。
为什么选择迭代中序：栈只保存尚未访问的祖先，
pre保存中序前驱。每弹出一个节点就完成一次相邻连接，不需要先收集到数组再做第二遍，也避免把head、pre放进对象成员后产生重复调用的残留状态。状态与不变量：每次弹出
cur时，head ... pre已经由所有访问过的节点组成一条升序双向链表，pre是链尾；cur是尚未访问节点中的最小值。连接pre.right = cur和cur.left = pre后，链表继续有序，cur成为新链尾。正确性：中序遍历保证节点按键值升序且每个节点恰好访问一次，因此按访问顺序连接后，所有相邻节点的前驱、后继都正确。遍历结束时
head是最小节点、pre是最大节点，再令head.left = pre、pre.right = head，首尾关系也正确，最终得到完整的循环双向链表。递归中序配合共享的
head、pre也能完成，代码稍短；迭代版本保持状态局部，面试中更容易说明栈空间和多次调用安全性。
解题步骤
- 空树直接返回
null。- 从根开始不断沿
left入栈，直到最左节点。- 弹出栈顶作为当前节点
cur：若pre为空，当前节点就是最小节点，记录为head；否则把pre与cur双向连接。- 更新
pre = cur，再转向当前节点原来的右子树，重复中序过程。- 遍历结束后，
head与pre分别是链表头尾，将它们双向连接成环并返回head。以
[4,2,5,1,3]为例，中序弹出顺序为1、2、3、4、5。访问时依次得到1 ⇄ 2 ⇄ 3 ⇄ 4 ⇄ 5，最后连接1.left = 5与5.right = 1。单节点树也会由同一收尾逻辑变成左右都指向自己的环。
代码实现
class Solution {
public Node treeToDoublyList(Node root) {
if (root == null) {
return null;
}
Deque<Node> stack = new ArrayDeque<>();
Node cur = root;
Node head = null;
Node pre = null;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if (pre == null) {
head = cur;
} else {
pre.right = cur;
cur.left = pre;
}
pre = cur;
cur = cur.right;
}
head.left = pre;
pre.right = head;
return head;
}
}
func treeToDoublyList(root *Node) *Node {
if root == nil {
return nil
}
stack := make([]*Node, 0)
cur := root
var head, pre *Node
for cur != nil || len(stack) > 0 {
for cur != nil {
stack = append(stack, cur)
cur = cur.Left
}
cur = stack[len(stack)-1]
stack = stack[:len(stack)-1]
if pre == nil {
head = cur
} else {
pre.Right = cur
cur.Left = pre
}
pre = cur
cur = cur.Right
}
head.Left = pre
pre.Right = head
return head
}
复杂度分析
- 时间复杂度：$O(n)$。每个节点恰好入栈、出栈并连接一次。
- 空间复杂度：$O(h)$，其中
h是树高。显式栈最多保存一条根到叶的路径；平衡树为 $O(\log n)$，链状树最坏为 $O(n)$。
关键点总结
- “BST + 有序输出”优先利用中序遍历，不需要额外排序。
pre是中序序列中的前驱，不一定是树结构中的父节点。- 相邻节点要同时设置
pre.right和cur.left，不能只连一个方向。- 中序只得到开链；遍历结束后还必须用最小、最大节点闭环。
易错点总结
- 返回原来的
root：根节点不一定是最小值；[4,2,5,1,3]应返回节点 1。- 在读取右子树前覆盖
cur.right：尚未遍历的节点可能丢失。代码只改前驱pre.right，当前节点的原右指针要留到cur = cur.right时读取。- 只设置一个方向的指针：正向遍历可能看似正确，反向遍历会断链；每对相邻节点必须双向连接。
- 忘记首尾闭环：会得到普通双向链表；空树需提前返回，单节点则也必须闭成自环。
- 遍历过程中提前连接头尾：会把尚未处理的树指针变成环，后续中序遍历可能死循环；闭环只能放在遍历完成之后。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 98. 验证二叉搜索树 | 中等 | 中序 pre 比大小判定升序 |
| 114. 二叉树展开为链表 | 中等 | 前序原地改指针拉成单链表 |
| 173. 二叉搜索树迭代器 | 中等 | 显式栈把中序拆成惰性输出 |
| 230. 二叉搜索树中第 K 小的元素 | 中等 | 中序计数到第 k 个提前剪枝 |
| 426. 将二叉搜索树转化为排序的双向链表 | 中等 | 本题同题异号，要求完全一致 |
| 538. 把二叉搜索树转换为累加树 | 中等 | 反序中序累加后缀和 |
| 897. 递增顺序搜索树 | 简单 | 中序重排成只有右孩子的斜树 |
| 1038. 从二叉搜索树到更大和树 | 中等 | 反序中序累加，与 538 判题不同 |
| LCR 052. 递增顺序搜索树 | 简单 | 897 的 LCR 版本，可新建节点 |
| LCR 054. 把二叉搜索树转换为累加树 | 中等 | 538 的 LCR 版本，节点值域更大 |
| 剑指 Offer 54. 二叉搜索树的第k大节点 | 简单 | 逆中序取第 k 个，方向相反 |
| 面试题 04.05. 合法二叉搜索树 | 中等 | 98 的变体，需处理重复值 |
| 面试题 17.12. BiNode | 简单 | 中序原地改指针但只要单向链 |