题目描述
思路解析
一句话答案：LeetCode 538 把二叉搜索树转换为累加树的最优解是反中序遍历：按右、根、左的顺序访问，节点值恰好从大到小出现，维护一个运行累加和 sum，每到一个节点先把原值加进 sum、再把节点值改写成 sum。一趟遍历完成全部改写，时间 O(n)、空间 O(h) 递归栈。
累加树到底要算什么
给一棵二叉搜索树（BST），要把每个节点的值替换成：原值加上树中所有大于它的节点值之和。换句话说，每个节点都在问同一个问题——比我大的那些数加起来是多少。输出仍是这棵树本身，所有值就地改写，返回改造后的根。
为什么逐个节点单独求和是浪费
最直白的做法是对每个节点扫一遍全树，把比它大的值累加起来，n 个节点各扫一次就是 O(n²)。浪费在哪里很清楚：「比 12 大的数」和「比 11 大的数」这两个集合几乎完全重叠，暴力法把同一批大数反复加了一遍又一遍。只要能按从大到小的顺序处理节点，「比当前大的所有值之和」就变成一个可以滚动维护的量——每处理完一个节点就把它并进去，谁都不用重复加。
反中序遍历为什么恰好给出从大到小
二叉搜索树的定义保证：中序遍历（左、根、右）得到升序序列。把顺序整个镜像成右、根、左——先钻右子树、再访问根、最后进左子树——得到的自然是降序序列，这就是反中序遍历。降序意味着走到任何一个节点时，所有比它大的节点都恰好已经被访问过，它们的总和正好就是此刻的运行累加和 sum。BST 的有序性在这里不是背景设定，而是让「从大到小枚举」零额外成本实现的关键。
为什么必须先累加再赋值，顺序不能反
每个节点上只做两步：先 sum += 原值，再 node.val = sum。先加后赋的顺序是硬要求，因为新值的定义是原值加上比它大的和——必须把自己也算进去，先赋值再累加就会漏掉自身。另一个方向性的坑：用正常中序（左、根、右）访问是升序，累加出来的是「比它小的和」，整棵树全错——遍历方向和累加语义是绑死的。
复杂度与迭代写法
每个节点恰好访问一次、做常数次运算，时间 O(n)；递归栈深等于树高 h，平衡树 O(log n)，最坏退化成链 O(n)。
不想用递归可以改成显式栈的迭代版：一路向右压栈到底，弹出即访问（累加并改值），再转向该节点的左子树，逻辑与递归完全一致，空间同为 O(h)。若题目反过来要求「比它小的节点之和」，把遍历方向换回正常中序即可，累加框架原样保留。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
核心一句话：累加树 = 每个节点 = 原值 + 所有比它大的节点之和，反中序(右根左)降序累加。
原始 BST，所有节点还是原值。反中序遍历从最右下角（最大值 14）开始，按「右子树 → 根 → 左子树」访问，越访问越小。
反中序走到当前最大的未访问节点，原值 = 14（橙色）。它比所有还没访问的节点都大。先把累加和更新：sum = 0 + 14 = 14。
节点新值落定：14 → 14（蓝色=已累加）。新值 = 原值 14 + 比它大的节点之和 0。继续反中序访问下一个更小的节点。
反中序走到当前最大的未访问节点，原值 = 13（橙色）。它比所有还没访问的节点都大。先把累加和更新：sum = 14 + 13 = 27。
节点新值落定：13 → 27（蓝色=已累加）。新值 = 原值 13 + 比它大的节点之和 14。继续反中序访问下一个更小的节点。
反中序走到当前最大的未访问节点，原值 = 12（橙色）。它比所有还没访问的节点都大。先把累加和更新：sum = 27 + 12 = 39。
节点新值落定：12 → 39（蓝色=已累加）。新值 = 原值 12 + 比它大的节点之和 27。继续反中序访问下一个更小的节点。
反中序走到当前最大的未访问节点，原值 = 11（橙色）。它比所有还没访问的节点都大。先把累加和更新：sum = 39 + 11 = 50。
节点新值落定：11 → 50（蓝色=已累加）。新值 = 原值 11 + 比它大的节点之和 39。继续反中序访问下一个更小的节点。
反中序走到当前最大的未访问节点，原值 = 10（橙色）。它比所有还没访问的节点都大。先把累加和更新：sum = 50 + 10 = 60。
节点新值落定：10 → 60（蓝色=已累加）。新值 = 原值 10 + 比它大的节点之和 50。继续反中序访问下一个更小的节点。
反中序走到当前最大的未访问节点，原值 = 9（橙色）。它比所有还没访问的节点都大。先把累加和更新：sum = 60 + 9 = 69。
节点新值落定：9 → 69（蓝色=已累加）。新值 = 原值 9 + 比它大的节点之和 60。继续反中序访问下一个更小的节点。
反中序走到当前最大的未访问节点，原值 = 8（橙色）。它比所有还没访问的节点都大。先把累加和更新：sum = 69 + 8 = 77。
节点新值落定：8 → 77（蓝色=已累加）。新值 = 原值 8 + 比它大的节点之和 69。继续反中序访问下一个更小的节点。
反中序走到当前最大的未访问节点，原值 = 7（橙色）。它比所有还没访问的节点都大。先把累加和更新：sum = 77 + 7 = 84。
节点新值落定：7 → 84（蓝色=已累加）。新值 = 原值 7 + 比它大的节点之和 77。继续反中序访问下一个更小的节点。
反中序走到当前最大的未访问节点，原值 = 6（橙色）。它比所有还没访问的节点都大。先把累加和更新：sum = 84 + 6 = 90。
节点新值落定：6 → 90（蓝色=已累加）。新值 = 原值 6 + 比它大的节点之和 84。继续反中序访问下一个更小的节点。
反中序走到当前最大的未访问节点，原值 = 5（橙色）。它比所有还没访问的节点都大。先把累加和更新：sum = 90 + 5 = 95。
节点新值落定：5 → 95（蓝色=已累加）。新值 = 原值 5 + 比它大的节点之和 90。继续反中序访问下一个更小的节点。
反中序走到当前最大的未访问节点，原值 = 4（橙色）。它比所有还没访问的节点都大。先把累加和更新：sum = 95 + 4 = 99。
节点新值落定：4 → 99（蓝色=已累加）。新值 = 原值 4 + 比它大的节点之和 95。继续反中序访问下一个更小的节点。
反中序走到当前最大的未访问节点，原值 = 3（橙色）。它比所有还没访问的节点都大。先把累加和更新：sum = 99 + 3 = 102。
节点新值落定：3 → 102（蓝色=已累加）。新值 = 原值 3 + 比它大的节点之和 99。继续反中序访问下一个更小的节点。
反中序走到当前最大的未访问节点，原值 = 2（橙色）。它比所有还没访问的节点都大。先把累加和更新：sum = 102 + 2 = 104。
节点新值落定：2 → 104（蓝色=已累加）。新值 = 原值 2 + 比它大的节点之和 102。继续反中序访问下一个更小的节点。
反中序走到当前最大的未访问节点，原值 = 1（橙色）。它比所有还没访问的节点都大。先把累加和更新：sum = 104 + 1 = 105。
最后一个节点：原值 1，新值 = 105（= 原值 1 + 比它大的所有节点之和 104）。整棵累加树改造完成，累加和最终 = 105。
累加树改造完成（绿色=已转换）。最大节点新值 = 它自己，越小的节点累加了越多更大节点之和，最左下角最小节点新值 = 全部之和 105。
边界都落在「没有更大节点」的情形，想清楚就不会错。
两个高频追问：迭代写法、对称变体。
参考代码
def convertBST(root): sum = 0 def dfs(node): nonlocal sum if not node: return dfs(node.right) # 先右(更大) sum += node.val # 并入累加和 node.val = sum # 新值 = 累加和 dfs(node.left) # 再左(更小) dfs(root) return root复杂度
- 时间：O(n)，每个节点恰好访问一次
- 空间：O(H)，递归栈深 = 树高 H；最坏退化链 O(n)，平衡树 O(log n)
易错点
面试追问把动画讲成自己的话
追问不用递归怎么做？
追问如果要求的是「比它小的节点之和」而不是更大，怎么改？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
二叉树展开为链表
LeetCode 114 · 中等 · 沿着 树 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题