把二叉搜索树转换为累加树 图解题解

累加树到底要算什么

给一棵二叉搜索树（BST），要把每个节点的值替换成：原值加上树中所有大于它的节点值之和。换句话说，每个节点都在问同一个问题——比我大的那些数加起来是多少。输出仍是这棵树本身，所有值就地改写，返回改造后的根。

为什么逐个节点单独求和是浪费

最直白的做法是对每个节点扫一遍全树，把比它大的值累加起来，n 个节点各扫一次就是 O(n²)。浪费在哪里很清楚：「比 12 大的数」和「比 11 大的数」这两个集合几乎完全重叠，暴力法把同一批大数反复加了一遍又一遍。只要能按从大到小的顺序处理节点，「比当前大的所有值之和」就变成一个可以滚动维护的量——每处理完一个节点就把它并进去，谁都不用重复加。

反中序遍历为什么恰好给出从大到小

二叉搜索树的定义保证：中序遍历（左、根、右）得到升序序列。把顺序整个镜像成右、根、左——先钻右子树、再访问根、最后进左子树——得到的自然是降序序列，这就是反中序遍历。降序意味着走到任何一个节点时，所有比它大的节点都恰好已经被访问过，它们的总和正好就是此刻的运行累加和 sum。BST 的有序性在这里不是背景设定，而是让「从大到小枚举」零额外成本实现的关键。

为什么必须先累加再赋值，顺序不能反

每个节点上只做两步：先 sum += 原值，再 node.val = sum。先加后赋的顺序是硬要求，因为新值的定义是原值加上比它大的和——必须把自己也算进去，先赋值再累加就会漏掉自身。另一个方向性的坑：用正常中序（左、根、右）访问是升序，累加出来的是「比它小的和」，整棵树全错——遍历方向和累加语义是绑死的。

复杂度与迭代写法

每个节点恰好访问一次、做常数次运算，时间 O(n)；递归栈深等于树高 h，平衡树 O(log n)，最坏退化成链 O(n)。

不想用递归可以改成显式栈的迭代版：一路向右压栈到底，弹出即访问（累加并改值），再转向该节点的左子树，逻辑与递归完全一致，空间同为 O(h)。若题目反过来要求「比它小的节点之和」，把遍历方向换回正常中序即可，累加框架原样保留。

Python

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

C++

class Solution {
    int sum = 0;
public:
    TreeNode* convertBST(TreeNode* root){
        if(!root) return root;
        convertBST(root->right);   // 先右(更大)
        sum += root->val;          // 并入累加和
        root->val = sum;           // 新值 = 累加和
        convertBST(root->left);    // 再左(更小)
        return root;
    }
};

Java

class Solution {
    private int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if (root == null) return root;
        convertBST(root.right);   // 先右(更大)
        sum += root.val;          // 并入累加和
        root.val = sum;           // 新值 = 累加和
        convertBST(root.left);    // 再左(更小)
        return root;
    }
}