题目描述
思路解析
一句话答案：LeetCode 897 递增顺序搜索树：BST 中序遍历天然升序，边走边把每个节点接到 prev 右指针、清掉左指针、prev 前移，一趟原地串成只有右孩子的递增链，时间 O(n)。
把一棵 BST 重排成只有右孩子的升序链
给一棵二叉搜索树 root，即每个节点左子树都比它小、右子树都比它大。要把它重排成递增顺序搜索树：最小的节点当新根，之后每个节点都没有左孩子、只挂一个右孩子，是一条从小到大的右斜链。题面例子 root=[50,30,80,20,40,70,90]，重排后是 20→30→40→50→70→80→90 这条单链，节点没变，只重接了指针。
先中序取值再新建树，为什么想省一趟
把 BST 的值从小到大取出并不难：中序遍历一趟，也就是按左孩子、自己、右孩子的顺序走，读到的值天然升序，存进数组，再照它新建一串只有右孩子的节点就行。这样能过，却走了两趟、还多造一整棵树。既然中序里节点已按升序一个个冒出来，能不能就地把它们串好，不另开数组、不新建节点。
中序遍历 BST，读出来为什么正好从小到大
关键在 BST 和中序的关系上。中序对任何节点都是先走完左子树，再访问自己，最后走右子树；而 BST 里左子树全比自己小、右子树全比自己大，于是小的先访问、大的最后访问，访问顺序恰好从小到大。所以中序里相邻两节点，前一个一定比后一个小——接到前一个右边就是升序链。
遍历到每个节点时，prev 和 dummy 各接什么
用 prev 记住上一个访问过的节点。中序递归 dfs 到某节点、左子树已走完时，轮到访问它：先接到 prev 右指针后面（prev.right = 当前节点），再清空它的左指针，最后 prev 前移到它，然后递归右子树。
第一个被访问的节点没有上一个可接，为省特判，开头先造一个虚拟头 dummy 让 prev 起步就指向它；走完后 dummy 的右孩子就是新链头，返回即可。
拿题面示例的七个节点亲手穿线
这棵树 50 是根，30、80 是左右孩子，20、40 挂在 30 下，70、90 挂在 80 下。prev 先指向 dummy，中序从根一路向左走到最小的 20：dummy.right 接 20，清空 20 左指针，prev 挪到 20。回到 30：20.right 接 30，prev 到 30，再去右孩子 40：30.right 接 40，prev 到 40。回到 50：40.right 接 50，prev 到 50。
右半边同理：50.right 接 70、prev 到 70；70.right 接 80、prev 到 80；80.right 接 90。中序走完，从 dummy.right 起就是 20→30→40→50→70→80→90，最左下的 20 成新根，每个节点只剩右孩子。
清左指针和 prev 前移，漏一个链就废了
接右指针和清左指针得成对做。只写 prev.right、忘了清空当前节点左指针，新链里就残留原来的左子树，可能绕成环。prev 前移也不能漏——否则后面每个节点都往同一处右边接、互相覆盖，最后只剩一个。
复杂度上，中序把每个节点访问一次、接线常数步，时间 O(n)；额外只用一个 dummy 哨兵，占用随递归栈层数，即树高 h，记 O(h)，歪成一条链时到 O(n)。边界也想清：单节点原样返回；只挂左孩子时最小的提成新根；本已是右斜链则不变。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这套「中序天然升序、逐个接到 prev 右边、清空左指针、prev 前移」，下面每一帧都在套它。
准备 · 虚拟头：开局先造一个虚拟头结点，让 prev 指向它，递归栈和藤蔓链都还是空的。接下来从根节点 50 出发，按「左、根、右」的中序顺序走，一路先往最左下钻。
下行压栈 · 50：中序要「先把左边走完」，所以把 50 压进递归栈，再往它的左孩子 30 继续下探。栈里现在等着 50。
下行压栈 · 30：中序要「先把左边走完」，所以把 30 压进递归栈，再往它的左孩子 20 继续下探。栈里现在等着 50、30。
下行压栈 · 20：中序要「先把左边走完」，所以把 20 压进递归栈，它已经没有左孩子了，左边到底，下一步该回头把栈顶的 20 真正访问掉。
中序访问 · 20：左边已经走干净，弹出栈顶 20，这就是当前中序序列里轮到的节点（高亮）。它前面比它小的节点都处理完了，所以 20 是眼下藤蔓链该接的下一个值。
接入藤蔓 · 20：把 20 接到上一个节点（prev = 虚拟头）的右指针后面，同时把 20 自己的左指针清空，让它在新链里只剩右孩子。20 标绿，表示已经进了藤蔓链：20。然后 prev 前移到 20，20 没有右子树，回头继续弹栈。
中序访问 · 30：左边已经走干净，弹出栈顶 30，这就是当前中序序列里轮到的节点（高亮）。它前面比它小的节点都处理完了，所以 30 是眼下藤蔓链该接的下一个值。
接入藤蔓 · 30：把 30 接到上一个节点（prev = 20）的右指针后面，同时把 30 自己的左指针清空，让它在新链里只剩右孩子。30 标绿，表示已经进了藤蔓链：20 → 30。然后 prev 前移到 30，接着去处理 30 的右子树（从 40 开始）。
下行压栈 · 40：中序要「先把左边走完」，所以把 40 压进递归栈，它已经没有左孩子了，左边到底，下一步该回头把栈顶的 40 真正访问掉。
中序访问 · 40：左边已经走干净，弹出栈顶 40，这就是当前中序序列里轮到的节点（高亮）。它前面比它小的节点都处理完了，所以 40 是眼下藤蔓链该接的下一个值。
接入藤蔓 · 40：把 40 接到上一个节点（prev = 30）的右指针后面，同时把 40 自己的左指针清空，让它在新链里只剩右孩子。40 标绿，表示已经进了藤蔓链：20 → 30 → 40。然后 prev 前移到 40，40 没有右子树，回头继续弹栈。
中序访问 · 50：左边已经走干净，弹出栈顶 50，这就是当前中序序列里轮到的节点（高亮）。它前面比它小的节点都处理完了，所以 50 是眼下藤蔓链该接的下一个值。
接入藤蔓 · 50：把 50 接到上一个节点（prev = 40）的右指针后面，同时把 50 自己的左指针清空，让它在新链里只剩右孩子。50 标绿，表示已经进了藤蔓链：20 → 30 → 40 → 50。然后 prev 前移到 50，接着去处理 50 的右子树（从 80 开始）。
下行压栈 · 80：中序要「先把左边走完」，所以把 80 压进递归栈，再往它的左孩子 70 继续下探。栈里现在等着 80。
下行压栈 · 70：中序要「先把左边走完」，所以把 70 压进递归栈，它已经没有左孩子了，左边到底，下一步该回头把栈顶的 70 真正访问掉。
中序访问 · 70：左边已经走干净，弹出栈顶 70，这就是当前中序序列里轮到的节点（高亮）。它前面比它小的节点都处理完了，所以 70 是眼下藤蔓链该接的下一个值。
接入藤蔓 · 70：把 70 接到上一个节点（prev = 50）的右指针后面，同时把 70 自己的左指针清空，让它在新链里只剩右孩子。70 标绿，表示已经进了藤蔓链：20 → 30 → 40 → 50 → 70。然后 prev 前移到 70，70 没有右子树，回头继续弹栈。
中序访问 · 80：左边已经走干净，弹出栈顶 80，这就是当前中序序列里轮到的节点（高亮）。它前面比它小的节点都处理完了，所以 80 是眼下藤蔓链该接的下一个值。
接入藤蔓 · 80：把 80 接到上一个节点（prev = 70）的右指针后面，同时把 80 自己的左指针清空，让它在新链里只剩右孩子。80 标绿，表示已经进了藤蔓链：20 → 30 → 40 → 50 → 70 → 80。然后 prev 前移到 80，接着去处理 80 的右子树（从 90 开始）。
下行压栈 · 90：中序要「先把左边走完」，所以把 90 压进递归栈，它已经没有左孩子了，左边到底，下一步该回头把栈顶的 90 真正访问掉。
中序访问 · 90：左边已经走干净，弹出栈顶 90，这就是当前中序序列里轮到的节点（高亮）。它前面比它小的节点都处理完了，所以 90 是眼下藤蔓链该接的下一个值。
接入藤蔓 · 90：把 90 接到上一个节点（prev = 80）的右指针后面，同时把 90 自己的左指针清空，让它在新链里只剩右孩子。90 标绿，表示已经进了藤蔓链：20 → 30 → 40 → 50 → 70 → 80 → 90。然后 prev 前移到 90，90 没有右子树，回头继续弹栈。
完成 · 藤蔓成形：中序走完，七个节点按 20、30、40、50、70、80、90 的升序依次接成了一条右斜链。最左下的 20 成了新根，每个节点都只有右孩子。返回虚拟头的右孩子 20，整道题就解完了。
边界先想清：单节点直接返回；只有左孩子时最小的会被提成新根；已经是右斜链则保持不变。
面试重点：讲清 dummy 为何省事，以及递归、迭代、Morris 三种中序的取舍。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def increasingBST(self, root: TreeNode) -> TreeNode: def dfs(root): if root is None: return nonlocal prev dfs(root.left) prev.right = root root.left = None prev = root dfs(root.right) dummy = prev = TreeNode(right=root) dfs(root) return dummy.right复杂度
- 时间：O(n)，中序遍历把每个节点恰好访问一次，接线是常数操作
- 空间：O(h)，递归栈深 = 树高 h；平衡时 O(log n)，退化成链时最坏 O(n)。不新建结果链里的业务节点，只额外用一个 dummy 哨兵结点，原地改指针
易错点
面试追问把动画讲成自己的话
追问为什么要引入虚拟头结点 dummy？不能直接用第一个节点吗？
追问除了递归，还有别的中序遍历写法吗？空间能不能更省？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
单值二叉树
LeetCode 965 · 简单 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题