如何把二叉搜索树转换为累加树或更大和树？

简化版

BST 中序是升序，反向中序就是从大到小访问。维护一个累加和 sum，按右、根、左遍历，每访问节点就把 sum += node.val，再把节点值改成 sum，即可得到累加树。

详细版

累加树通常要求每个节点的新值等于原树中所有大于等于它的节点值之和。BST 中「比当前节点大的值」都位于中序序列的右侧，所以按降序访问最自然。

步骤：

先递归处理右子树，访问所有更大的值；
当前节点原值加入全局累加和；
当前节点值改为累加和；
再处理左子树，让较小节点累加到更多大值。

时间复杂度 O(n)，递归栈空间 O(h)，通常可以原地修改节点。若题目定义是「严格大于」而不是「大于等于」，赋值顺序要略微调整。

完整版教学

一、累加树到底在累加什么

累加树的常见定义是：每个节点的新值等于原 BST 中所有「大于等于当前值」的节点值之和。比如中序序列 [2,5,13]，转换后应变成 [20,18,13]：值 13 没有更大的数，新值 13；值 5 加上 13 得到 18；值 2 加上 5 和 13 得到 20。

这题容易被树形结构绕晕，其实它在有序序列上非常简单：从右往左做后缀和。BST 的反向中序正好就是从最大值扫到最小值。

记忆钩子：累加树不是从根开始累加，而是从「最大节点」往回做后缀和；方向错了，值就全错。

二、为什么要用反向中序

普通中序是左、根、右，得到升序。反向中序是右、根、左，得到降序。当前访问到某个节点时，所有比它大的节点都已经访问过，并且它们的和保存在 sum 里。此时把当前原值加入 sum，就得到「大于等于当前值」的总和。

用 [2,5,13] 推一遍：

访问 13: sum=0+13=13，节点 13 -> 13
访问 5 : sum=13+5=18，节点 5  -> 18
访问 2 : sum=18+2=20，节点 2  -> 20

这个过程和数组后缀和完全一致，只是数组下标被树的遍历顺序替代了。

三、代码实现中的赋值顺序

代码必须先保存或使用当前原值，再修改节点值。因为一旦把 node.val 改成累加和，原始值就丢了。如果后续还要用原值，就要提前存到变量。

int sum = 0;

TreeNode convertBST(TreeNode root) {
    reverseInorder(root);
    return root;
}

void reverseInorder(TreeNode node) {
    if (node == null) return;
    reverseInorder(node.right);
    sum += node.val;
    node.val = sum;
    reverseInorder(node.left);
}

这段代码是原地修改，返回的根节点还是原来的根。面试时要说明 sum 是遍历过程的外部状态，不能在每层递归里重新定义，否则累加会断掉。

四、严格大于和大于等于有什么差别

有些题叫「累加树」，要求包含自身；有些题叫「更大和树」，可能要求节点新值等于严格大于它的值之和，是否包含自身要看题目描述。两者只差赋值顺序，但语义完全不同。

定义	当前节点新值	操作顺序
大于等于当前值	`sum + oldVal`	先加当前值，再赋值
严格大于当前值	`sum`	先赋值为 sum，再加当前原值

严格大于版本可以写成：

int old = node.val;
node.val = sum;
sum += old;

面试里这个细节非常容易成为追问点，答题前先确认题目口径最稳。

五、为什么不能从小到大累加

如果按普通中序从小到大访问，访问值 2 时，你还不知道 5 和 13 的和，除非提前把总和算出来。可以先求全树总和，再从小到大做「剩余和」更新，但这需要两次遍历，且更绕。反向中序一次遍历就能在访问当前节点时已经拥有所有更大值的信息。

从信息流角度看，当前节点需要依赖右侧所有更大节点，所以遍历顺序应该让依赖先完成。反向中序正是这种拓扑顺序：右子树先处理，根再处理，左子树最后处理。

六、复杂度和树形变化

算法只访问每个节点一次，时间 O(n)。递归栈空间 O(h)，h 是树高。它只改节点值，不改指针结构，所以树的形状完全不变，但修改后通常不再满足原来的 BST 有序性质。比如 [2,5,13] 变成 [20,18,13]，中序不再升序。

这一点在工程场景很重要：转换后的树不适合继续当 BST 做查找。如果后续还要查询原始 BST，应复制一棵树或保存原值，而不是直接原地改。

七、常见误区与追问

误区：累加树应该从根节点开始累加。 根不一定是最大值，从根开始无法保证已见过所有更大节点。
追问：为什么遍历顺序是右根左？ 因为它对应降序访问，当前节点所需的更大值已经累加完成。
误区：转换后仍然是合法 BST。 节点值被改成后缀和后，中序通常不再升序。
追问：严格大于和大于等于如何改代码？ 严格大于先赋值再累加原值，大于等于先累加再赋值。
误区：sum 可以定义在递归函数内部。 那会导致每层递归重新开始累加，必须是跨调用共享状态。

八、加强记忆

把累加树想成 BST 中序数组的「后缀和」。普通中序是升序，反向中序是降序；从最大值开始维护一个累计和，访问当前节点时更大的值都已经进入 sum。包含自身就先加后赋值，严格大于就先赋值后加原值。真正容易错的不是代码长度，而是遍历方向和赋值顺序。

简化版

详细版