LeetCode 剑指 Offer 36. 二叉搜索树与双向链表
题目描述
题意分析
将二叉搜索树转换为按节点值从小到大排列的循环双向链表，返回最小值节点。直接复用树中的节点：
left改作前驱指针，right改作后继指针，不能另建一批节点代替。双向要求相邻节点能互相到达，循环还要求最小节点的前驱指向最大节点、最大节点的后继指回最小节点。空树返回空；只有一个节点时，它的左右指针都应指向自己。
解法：迭代中序原地串联
核心思路
[!blue]
二叉搜索树的中序遍历顺序就是从小到大的顺序，因此可以边遍历边把相邻节点串起来，不需要收集全部节点后再排序。用显式栈保存尚未处理的祖先，先不断向左入栈，弹出节点时再处理它，随后转入右子树。
用
pre指向刚刚访问过的中序节点，用head保存第一个被访问的节点。第一次弹出时还没有前驱，这个节点就是最小节点，记录为head；以后每次弹出cur，都令pre.right = cur、cur.left = pre，在两个方向连接相邻节点，然后令pre = cur。原地重连不会破坏剩余遍历：访问
cur时，它的左子树已经处理完，所以可以把cur.left改为前驱；当前节点原来的right尚未覆盖，仍能用它进入未遍历的右子树。若前驱原来有右子树，算法此时已经沿那棵子树下行，待处理位置由当前节点与栈共同保存，因此改写前驱的右指针也不会丢失入口。这些连接逐步形成从
head到pre的有序双向前缀。中序结束后，pre就是最大节点，再执行head.left = pre与pre.right = head，补上首尾两条循环连接。闭环必须留到最后，否则沿原树指针继续遍历时可能重新进入已经处理过的节点。每个节点只在中序弹出时接入一次，节点顺序与 BST 的有序顺序一致。单节点时
head与pre相同，最后两次赋值自然形成自环，也不需要额外分支。
解题步骤
- 空树直接返回空，非空时初始化栈、当前指针
cur，以及空的head、pre。- 从
cur不断向左入栈，直到没有左孩子，再弹出栈顶作为当前访问节点。- 若
pre为空，记录head = cur；否则将pre与cur双向相连。- 更新
pre = cur，再进入当前节点原来的右子树，重复中序过程。- 当前指针与栈都为空后，将
head、pre首尾相连并返回head。
代码实现
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)$。
关键点总结
[!green]
- “BST + 有序输出”优先利用中序遍历，不需要额外排序。
pre是中序序列中的前驱，不一定是树结构中的父节点。- 相邻节点要同时设置
pre.right和cur.left，不能只连一个方向。- 中序只得到开链；遍历结束后还必须用最小、最大节点闭环。
易错点总结
[!yellow]
- 返回原根节点：BST 的根未必最小，应返回中序第一个访问到的
head。- 提前覆盖
cur.right：当前节点原来的右子树还需要遍历，本步只改前驱的右指针与当前节点的左指针。- 只连接一个方向：必须同时设置前驱的后继与当前节点的前驱，才能形成双向链表。
- 忽略循环要求：普通的有序双向链还不够，遍历后必须补上头尾连接，单节点也需要自环。
- 遍历中途闭环：会让仍在使用的树指针形成回路，闭环应放在中序处理全部结束之后。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 897. 递增顺序搜索树 | 简单 | 同样按BST中序重连节点，原题只连递增右链，本题还要连接前驱及首尾成环。 |
| 114. 二叉树展开为链表 | 中等 | 同样原地重连树节点，原题按前序展开普通二叉树，本题按中序生成有序双向链。 |