把二叉搜索树转换为累加树

问题拆解

每个节点要换成「原树中所有大于等于它的值之和」。若对每个节点都去搜集比它大的节点，会做大量重复工作。真正该利用的是二叉搜索树的有序性。

普通中序遍历（左→根→右）会按值从小到大访问节点。而这道题关心的是「比当前值大的部分」，所以把顺序倒过来：右→根→左，节点就会按从大到小的次序出现。

一旦访问顺序是从大到小，「大于等于当前节点的和」就等于「到目前为止累加的总和」，用一个变量顺着记下来即可。

反序中序 + 累加变量

def convertBST(root):
    total = 0

    def visit(node):
        nonlocal total
        if not node:
            return
        visit(node.right)
        total += node.val
        node.val = total
        visit(node.left)

    visit(root)
    return root

三行遍历顺序是关键：先递归右子树，再处理当前节点，最后递归左子树。处理当前节点时，total 已经累加了所有更大的值，加上自己后写回，就是这个节点的新值。整棵树只需走一遍。

复杂度

指标	复杂度	原因
时间	O(n)	反序中序遍历访问每个节点一次
空间	O(h)	递归栈深度等于树高

可以迁移的模式

• 二叉搜索树的中序遍历天然有序，正序取小、反序取大，选对方向能省掉排序；
• 遍历过程中携带一个累加/前驱变量，可以把「与其他节点的关系」摊平成一路扫描；
• 当题目问的是「所有比我大/小的元素之和」时，先想能不能用一次有序遍历前缀式地算出来。

顺序遍历配一个滚动状态，是处理有序结构上「前缀 / 后缀聚合」的顺手工具。