题目描述
思路解析动画文字版
记牢这套「中序天然升序、逐个接到 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题