题目描述
思路解析动画文字版
最直接的想法：对每个节点，都遍历整棵树一遍，把比它大的值全加起来。n 个节点各扫一遍全树，就是大O n 平方，节点一多就超时。
关键洞察：BST 的中序遍历(左→根→右)结果天然有序，从小到大。把它对调成右→根→左，就是从大到小。从最大值开始走，一路累加，每个节点要的「更大节点之和」就已经现成攒好了。
原始 BST · 先看清结构：这是原始 BST。把它按反中序排开，访问顺序是 7、6、5、4、2、1、0，正好从大到小。下面就逐个节点慢放这个过程。
灵魂帧 ① · 访问 7（最大，先走到最右）：递归一路往右，先抵达最右下角的 7。它是全树最大，前面没有更大的节点。total 从 0 加上 7 变成 7，节点 7 写回 7，值不变。
灵魂帧 ② · 回到 6（右子树的根）：7 走完，弹回到父节点 6。此刻 total 已经攒着 7，加上 6 自己变成 13。节点 6 写回 13，正好是它自己加上唯一比它大的 7。
灵魂帧 ③ · 下到 5（6 的左孩子）：6 改完后进它的左孩子 5。total 里已经攒了 7 和 6 共 13，加上 5 变成 18。节点 5 写回 18。注意 total 是跨递归共享的，从头攒到现在没清零。
灵魂帧 ④ · 回到根 4，再去左子树：右子树全部走完，递归回到根节点 4。total 此刻是 18，加上 4 变成 22。节点 4 写回 22，等于它自己加上右边那三个更大的节点。接下来才轮到左子树。
灵魂帧 ⑤ · 左子树从最大的 2 开始：进入左子树，规则一样：先走到这片子树的最右节点 2。total 是 22，加 2 变成 24。节点 2 写回 24。左子树里 2 最大，所以它在左子树里第一个被处理。
灵魂帧 ⑥ · 收尾 1、0（最小的累加最多）：最后是子树根 1 和最左的 0。1 让 total 变 25，节点 1 写回 25。0 加上去 total 仍是 25，节点 0 也写 25。最小的节点前面所有人都比它大，所以它累加得最多。
灵魂帧 ⑦ · 累加树完成：整棵树改造完成。回头看：核心就是把中序的左右两步对调成反中序，再配一个从头攒到尾、跨递归共享的 total。每访问一个节点，先加它、再用 total 改写它的值。
一句话本质：BST 反中序按从大到小访问，维护一个跨递归的 total，每到一个节点先把它加进 total、再用 total 写回这个节点。
雷区实演 · 顺序写反会怎样：拿节点 6 真跑一遍坑：此刻 total 是 7。正确顺序先加再写，6 得到 13。如果顺序写反，先写回的是 7、再累加，节点 6 就少了自己的 6，错成 7。一字之差，整棵树偏。
边界三连：三个边界：空树直接返回；单节点不变；最小的三节点树验证累加方向。最小的 1 累加最多变 6，符合规律。
面试追问：面试追问重点：迭代写法、为何选反中序、与中序的关系。把动画里的 total 含义讲成自己的话就稳了。
迁移阶梯：学会这招，去做 LC1038(同题)、LC230(BST 第 k 小，用正中序计数)、LC99(恢复 BST，中序找逆序对)。都是「BST 中序天然有序」这条性质的变体。点开 AI 助教可以让它出一道同型题考你。
参考代码
class Solution: def convertBST(self, root): total = 0 def dfs(node): nonlocal total if not node: return dfs(node.right) # 先走右(更大) total += node.val # 累加 node.val = total # 写回 dfs(node.left) # 再走左 dfs(root) return root复杂度
- 时间复杂度：O(n)，每个节点恰好访问一次，n 个节点就 n 次
- 空间复杂度：O(h)，递归栈深 ＝ 树高 h；平衡树 O(log n)，退化成链最坏 O(n)
可套用的代码模板
这是可背的骨架，不是抄答案：BST 遍历题只要决定两件事——左右顺序(升序还是降序)，和 visit 里干什么(累加 / 计数 / 比较前驱)。538 就是右、累加写回、左。
# BST 有序遍历通用骨架：把 ___ 换成本题逻辑def inorder(node): if not node: return inorder(node.___) # 538 填 right(降序)；正序填 left visit(node) # 538: total+=val; val=total inorder(node.___) # 538 填 left；正序填 right易错点
面试追问把动画讲成自己的话
追问能不能不用递归、改成迭代？
追问为什么用「反中序」而不是先求总和再减？
追问和普通中序遍历差在哪？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
二叉树展开为链表
LeetCode 114 · 中等 · 沿着 树 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题