把二叉搜索树转换为累加树 图解题解
倒着走一遍 BST，一个累加变量就能把每个节点改写完毕。
BST 里按「右→根→左」倒着中序走，就像读排行榜从第一名往后翻：先见到最大的，边走边攒一个累计积分。轮到某个人时，比他强的都已经算进积分里了，把自己的值往上一加，新积分就是题目要的结果。整棵树只走一遍，一个临时变量从头攒到尾，不回头不重查。
这道题到底在问什么
- 输入 root
- [4,1,6,0,2,5,7]
- 输出
- [22,25,13,25,24,18,7]
最优解：一步一步想明白
- 3最直接的想法：对每个节点，都遍历整棵树一遍，把比它大的值全加起来。n 个节点各扫一遍全树，就是大O n 平方，节点一多就超时。
- 4关键洞察：BST 的中序遍历(左→根→右)结果天然有序，从小到大。把它对调成右→根→左，就是从大到小。从最大值开始走，一路累加，每个节点要的「更大节点之和」就已经现成攒好了。
- 5目标：新值 ＝ 原值 ＋ 所有更大节点之和这是原始 BST。把它按反中序排开，访问顺序是 7、6、5、4、2、1、0，正好从大到小。下面就逐个节点慢放这个过程。
- 6total ＝ 0 → 加 7 → total ＝ 7，节点 7 写回 7递归一路往右，先抵达最右下角的 7。它是全树最大，前面没有更大的节点。total 从 0 加上 7 变成 7，节点 7 写回 7，值不变。
- 7total ＝ 7 → 加 6 → total ＝ 13，节点 6 写回 137 走完，弹回到父节点 6。此刻 total 已经攒着 7，加上 6 自己变成 13。节点 6 写回 13，正好是它自己加上唯一比它大的 7。
- 8total ＝ 13 → 加 5 → total ＝ 18，节点 5 写回 186 改完后进它的左孩子 5。total 里已经攒了 7 和 6 共 13，加上 5 变成 18。节点 5 写回 18。注意 total 是跨递归共享的，从头攒到现在没清零。
- 9total ＝ 18 → 加 4 → total ＝ 22，节点 4 写回 22右子树全部走完，递归回到根节点 4。total 此刻是 18，加上 4 变成 22。节点 4 写回 22，等于它自己加上右边那三个更大的节点。接下来才轮到左子树。
- 10total ＝ 22 → 加 2 → total ＝ 24，节点 2 写回 24进入左子树，规则一样：先走到这片子树的最右节点 2。total 是 22，加 2 变成 24。节点 2 写回 24。左子树里 2 最大，所以它在左子树里第一个被处理。
- 111：total ＝ 25；0：total ＝ 25（加 0 不变）最后是子树根 1 和最左的 0。1 让 total 变 25，节点 1 写回 25。0 加上去 total 仍是 25，节点 0 也写 25。最小的节点前面所有人都比它大，所以它累加得最多。
- 12原 [4,1,6,0,2,5,7] → [22,25,13,25,24,18,7]整棵树改造完成。回头看：核心就是把中序的左右两步对调成反中序，再配一个从头攒到尾、跨递归共享的 total。每访问一个节点，先加它、再用 total 改写它的值。
- 15一句话本质：BST 反中序按从大到小访问，维护一个跨递归的 total，每到一个节点先把它加进 total、再用 total 写回这个节点。
- 17若先写回再累加：节点 6 会错成 7（漏了自己的 6）拿节点 6 真跑一遍坑：此刻 total 是 7。正确顺序先加再写，6 得到 13。如果顺序写反，先写回的是 7、再累加，节点 6 就少了自己的 6，错成 7。一字之差，整棵树偏。
- 22学会这招，去做 LC1038(同题)、LC230(BST 第 k 小，用正中序计数)、LC99(恢复 BST，中序找逆序对)。都是「BST 中序天然有序」这条性质的变体。点开 AI 助教可以让它出一道同型题考你。
⚠️ 容易写错的地方
✗ 错：用普通中序(左→根→右)从小到大
✓ 对：用反中序(右→根→左)从大到小
要先把更大的节点累加进 total，所以必须先走右
✗ 错：total 写成 dfs 的局部变量 / 参数
✓ 对：用 nonlocal(Py) 或成员变量(C++/Java)
total 要跨所有递归调用共享，局部变量一返回就丢
✗ 错：先 node.val = total 再 total += node.val
✓ 对：先 total += node.val 再 node.val = total
顺序反了会漏加自己，新值就少了本节点的原值
完整代码（Python / C++ / Java）
Python
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 rootC++
class Solution {
int total = 0;
void dfs(TreeNode* node) {
if (!node) return;
dfs(node->right); // 先走右(更大)
total += node->val; // 累加
node->val = total; // 写回
dfs(node->left); // 再走左
}
public:
TreeNode* convertBST(TreeNode* root) {
dfs(root); return root;
}
};Java
class Solution {
int total = 0;
public TreeNode convertBST(TreeNode root) {
if (root == null) return null;
convertBST(root.right); // 先走右(更大)
total += root.val; // 累加
root.val = total; // 写回
convertBST(root.left); // 再走左
return root;
}
}套路模板 · BST 中序框架(挖空)
# 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// 改 visit 与左右顺序即可套用到 BST 各题
void inorder(TreeNode* node) {
if (!node) return;
inorder(node->___); // 538: right
visit(node); // 538: total+=val; val=total
inorder(node->___); // 538: left
}// 状态(total/k/前驱)做成员变量，跨递归共享
void inorder(TreeNode node) {
if (node == null) return;
inorder(node.___); // 538: right
visit(node); // 538: total+=val; val=total
inorder(node.___); // 538: left
}复杂度
时间复杂度
O(n)
每个节点恰好访问一次，n 个节点就 n 次
空间复杂度
O(h)
递归栈深 ＝ 树高 h；平衡树 O(log n)，退化成链最坏 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 把二叉搜索树转换为累加树 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能不用递归、改成迭代？+
可以。用一个显式栈做反中序(Morris 遍历也行)：一路把右孩子压栈到底，弹出时累加并写回，再转向左孩子。逻辑和递归完全一样，只是手动管理栈，空间仍是 O(h)，Morris 可做到 O(1)。
为什么用「反中序」而不是先求总和再减？+
先求总和、再对每个节点减去「小于等于它的和」也能做，但要么再排序、要么再扫一遍前缀和，更绕。反中序一次遍历就地完成，最简洁，是面试首选答案。
和普通中序遍历差在哪？+
只把左右两次递归对调(先右后左)，并在「访问」时做 total 累加 + 写回。框架就是中序遍历的镜像，记住这点就能秒推。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。