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

问题拆解

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

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

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

反序中序 + 累加变量

private int total = 0;

public TreeNode convertBST(TreeNode root) {
    if (root != null) {
        convertBST(root.right);
        total += root.val;
        root.val = total;
        convertBST(root.left);
    }
    return root;
}

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

func convertBST(root *TreeNode) *TreeNode {
    total := 0
    var visit func(node *TreeNode)
    visit = func(node *TreeNode) {
        if node == nil {
            return
        }
        visit(node.Right)
        total += node.Val
        node.Val = total
        visit(node.Left)
    }
    visit(root)
    return root
}

pub fn convert_bst(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
    fn visit(node: &Option<Rc<RefCell<TreeNode>>>, total: &mut i32) {
        if let Some(n) = node {
            let mut n = n.borrow_mut();
            visit(&n.right, total);
            *total += n.val;
            n.val = *total;
            visit(&n.left, total);
        }
    }
    let mut total = 0;
    visit(&root, &mut total);
    root
}

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

复杂度

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

可以迁移的模式

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

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