LeetCode 897. 递增顺序搜索树
题目描述
题意分析
按二叉搜索树的中序顺序重新连接原节点，让最左节点成为新根，所有节点的左孩子为空，右孩子依次指向下一个节点。结果是一条按值递增的右链，需要返回新根。
解法：迭代中序遍历 + 尾插重连指针
核心思路
[!blue]
二叉搜索树的左子树、根、右子树按中序访问就是有序序列，因此无需收集数值再排序。只要保持中序访问顺序，把每个访问到的原节点追加到右链尾部即可。
遍历使用游标
cur和显式栈：不断沿左孩子下降并压栈，直到没有左侧节点；此时栈顶就是下一个该访问的节点，它的左子树已经全部处理，清空左指针不会丢掉未访问节点。连接使用哨兵
dummy和尾指针tail。弹出节点后，先保存它的原右子树入口，供后续中序遍历使用；再清空它的左孩子，令tail.right指向它，最后把tail移到这个新尾部。哨兵让第一个节点与后续节点都能用同样的追加操作。已访问节点按中序形成了正确前缀，尚未访问部分的入口由游标和栈保留，所以修改前缀中的右指针不会影响后续遍历。只有游标为空且栈也为空时才遍历完毕；最后访问的最大节点原本没有右孩子，自然成为右链末尾，返回
dummy.right即可。
解题步骤
- 准备中序遍历栈、游标、哨兵和尾指针。
- 沿左链压栈，弹出当前最小未处理节点。
- 保存右子树入口，清空左指针并连接到链尾。
- 继续遍历，结束后返回哨兵的右孩子。
代码实现
class Solution {
public TreeNode increasingBST(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
TreeNode dummy = new TreeNode(0);
TreeNode tail = dummy;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop();
// 保存后续中序遍历所需的原右子树入口。
cur = node.right;
// 当前左子树已处理完成，清空左指针并把节点接到已访问链尾。
node.left = null;
tail.right = node;
tail = node;
}
return dummy.right;
}
}
func increasingBST(root *TreeNode) *TreeNode {
var stack []*TreeNode
cur := root
dummy := &TreeNode{}
tail := dummy
for cur != nil || len(stack) > 0 {
for cur != nil {
stack = append(stack, cur)
cur = cur.Left
}
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
// 保存后续中序遍历所需的原右子树入口。
next := node.Right
// 当前左子树已处理完成，清空左指针并把节点接到已访问链尾。
node.Left = nil
tail.Right = node
tail = node
cur = next
}
return dummy.Right
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点入栈、出栈各一次。
- 空间复杂度：$O(h)$，显式栈由原树高度决定。
关键点总结
[!green]
- 遍历负责取得中序顺序，尾指针负责连接已访问前缀。
- 当前左子树处理完后才能清空它的入口。
- 只有尾指针之前的部分已经连接完成，后续树入口由游标与栈保留。
易错点总结
[!yellow]
- 尾指针先移动，再连接它的右指针：会把节点连接到自己。
- 遗漏清空左指针：结果仍保留原树连接。
- 只根据游标非空决定循环结束：栈中可能还有待处理祖先。
- 返回原根：原根往往位于新链中间，前面的节点丢失。
- 重连时忘记保存右子树入口：遍历过程需要沿原树结构继续，不能丢掉尚未访问的右子树。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 114. 二叉树展开为链表 | 中等 | 同样原地连成链，本题按BST中序成为递增右链，原题按前序展开普通二叉树。 |
| 426. 将二叉搜索树转化为排序的双向链表 | 中等 | 同样按BST中序重连节点，原题连接为循环双向链表，本题只保留向右的单链。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！