LeetCode LCR 054. 把二叉搜索树转换为累加树

2026-03-28 HGNULB 约 7 分钟

文章信息 5 个分类 5 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 054. 把二叉搜索树转换为累加树

题意分析

题目目标：把二叉搜索树中每个节点的值替换成"原树中所有大于等于该节点值的节点值之和"，树的结构保持不变，返回原来的根。
核心约束：每个节点的新值只依赖于"值不小于它的那些节点"，而二叉搜索树按中序是升序排列的，所以按值从大到小的顺序访问节点时，需要的和恰好是一个只增不减的累计量。这说明遍历顺序一旦选对，整个问题就退化成一次简单的累加。
边界处理：树可能为空，直接返回空；最大的节点新值等于它自己；节点值可以为负数，因此累计量不单调递增的假设不能用来剪枝；节点数与值域相乘可能超出直觉，但题目范围内 32 位整型足够。
实现取舍：新值必须基于原值累加，而修改又是原地进行的——所以访问一个节点时，必须保证它的原值还没有被别人用过、也还没有被自己覆盖过，这要求"读原值、累加、写新值"三步紧挨着且只做一次。

解法：深度优先搜索

核心思路

朴素做法是先中序遍历收集所有值，再对每个节点二分或线性地求"大于等于它的后缀和"，需要额外数组，还要走两趟树。
观察需求："大于等于当前值的所有节点之和"，就是把节点按值降序排列后的一个前缀和。而二叉搜索树的中序是升序，把中序反过来——先右子树、再根、后左子树——得到的正是降序序列。既然是降序，那么每访问一个节点时，此前访问过的所有节点恰好就是"比它大的全部节点"。
由此确定不变量：用一个累计变量 s，在按降序访问到节点 x 的那一刻，s 的值恰好等于原树中所有严格大于 x.val 的节点值之和。于是执行 s += x.val 后，s 就变成了"大于等于 x.val 的节点值之和"，正是该节点要写入的新值；写完之后 s 又自然满足下一个（更小的）节点的不变量。
整个算法就是一次反序中序遍历加一个累加器：递归右子树、结算当前节点、递归左子树。s 必须是跨递归共享的（成员变量或闭包变量），因为它承载的是全局进度而不是局部信息。

解题步骤

准备一个初值为 0 的累计变量 s。为什么初值是 0：最大的那个节点之上没有任何更大的节点，它的新值应等于自身，0 + val 恰好成立。

递归入口遇到空节点直接返回。为什么不做任何事：空子树不含节点，既不该改变 s 也没有值需要写。

先递归右子树 dfs(root.right)。为什么右在最前：右子树里的值全都大于当前节点，它们必须先被累加进 s，当前节点的新值才是正确的。

然后执行 s += root.val 与 root.val = s。为什么必须先加后写：s += root.val 用的是节点的原值，一旦顺序颠倒先写了新值，累加就会把新值重复计入；两行之间也绝不能插入任何递归调用。

最后递归左子树 dfs(root.left)。为什么左在最后：左子树的值都小于当前节点，它们需要把当前节点也算进自己的累计中，所以必须在当前节点结算之后再走。

主函数返回原来的 root。为什么返回原根：题目只要求改值不改结构，节点对象和指针关系都没有变化。

以 具体用例：树 [4, 1, 6, 0, 2, 5, 7] 走一遍。降序访问顺序是 7、6、5、4、2、1、0。访问 7 时 s 从 0 变为 7，节点 7 写入 7。访问 6 时 s 变为 13，节点 6 写入 13。访问 5 时 s 变为 18，节点 5 写入 18。访问根 4 时 s 变为 22，根写入 22——此时右子树 5、6、7 都已结算完毕，正是先右后根的功劳。访问 2 时 s 变为 24，节点 2 写入 24。访问 1 时 s 变为 25，节点 1 写入 25。访问 0 时 s 变为 25，节点 0 写入 25。最终树为 [22, 25, 13, 25, 24, 18, 7]，逐个核对无误。

代码实现

// 核心实现：深度优先搜索，维护必要状态并避免重复处理。
class Solution {
    private int s;

    public TreeNode convertBST(TreeNode root) {
        dfs(root);
        return root;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.right);
        s += root.val;
        root.val = s;
        dfs(root.left);
    }
}

// 核心实现：深度优先搜索，维护必要状态并避免重复处理。
func convertBST(root *TreeNode) *TreeNode {
    s := 0
    var dfs func(*TreeNode)
    dfs = func(root *TreeNode) {
        if root == nil {
            return
        }
        dfs(root.Right)
        s += root.Val
        root.Val = s
        dfs(root.Left)
    }
    dfs(root)
    return root
}

复杂度分析

时间复杂度：$O(n)$。凭什么：每个节点恰好被访问一次，访问时只做一次加法和一次赋值，没有任何查找或二次遍历。

空间复杂度：$O(h)$，h 为树高，最坏（链状树）为 $O(n)$。凭什么：除一个整型累计变量外没有任何容器，唯一开销是递归调用栈。

关键点总结

二叉搜索树的"反序中序"（右、根、左）给出降序序列，凡是题目要求"比我大的元素的统计量"，都应该第一时间想到这条顺序，它把区间查询变成了顺序累加。

用一个跨递归共享的累计变量承载"已访问部分的聚合结果"，是把 $O(n^2)$ 的两两比较压成 $O(n)$ 的通用手段；关键是能一句话说清它在每个访问时刻的确切含义。

原地修改类问题的纪律是"读原值与写新值紧挨着"，中间不能插入任何会访问同一节点的递归，否则原值就被污染了。

累计变量必须是共享状态而不是参数副本或局部变量，这一点在 Go 的闭包与 Java 的成员变量写法上都要特别留意。

面试视角：面试官通常会问"能不能不用递归"。可以：用显式栈按右、根、左的顺序迭代，或者用 Morris 反序遍历把空间压到 $O(1)$。回答时先讲清"为什么是反序中序"，再给出递归实现，最后主动提一句 Morris，层次感就出来了。

易错点总结

错误写法：用正常中序（左、根、右）遍历累加 → 树 [1, 0, 2] 的正确结果是 [3, 3, 2]，实际得到 [1, 0, 3]，每个节点累加的是比它小的部分。

错误写法：把 s += root.val 与 root.val = s 写反成 root.val = s; s += root.val; → 树 [1] 中根先被写成 0 再累加 0，返回 [0] 而不是 [1]。

错误写法：在两行结算之间插入递归调用，如 s += root.val; dfs(root.left); root.val = s; → 左子树的值被提前算进当前节点，树 [1, 0] 中根写成 1 之后又被左子树污染，结果错乱。

错误写法：把 s 作为参数按值传递 → 每层递归拿到的是副本，右子树累加的结果传不回来，树 [1, 0, 2] 的根只得到自身值 1。

错误写法：Java 中把 s 声明为 dfs 的局部变量 → 每次调用都从 0 开始，所有节点的新值都等于自己原来的值。

错误写法：递归右子树写成 dfs(root.left)（左右写反） → 相当于退化成正常中序，结果同第一条，方向整体反了。

错误写法：先把所有值收集到数组求后缀和，再按中序回填时误用了升序对应关系 → 树 [1, 0, 2] 回填成 [2, 3, 3]，节点与和的配对错位。

错误写法：认为节点值非负，用"累计和大于某阈值就停止"做剪枝 → 树中存在负值时（如 [0, -4, 4]）累计和不单调，剪枝会漏掉后续节点。

错误写法：返回 dfs 的结果而不是原 root，且 dfs 声明为无返回值 → 编译错误或返回空树，题目要求返回的是原根。

错误写法：漏掉 root == null 的判断 → 空树输入时访问 root.right 直接空指针异常。

相似题目

题目	难度	考察点
LCR 053. 二叉搜索树中的中序后继	中等	同样利用有序性定位"更大"的节点，但只需一次下行
108. 将有序数组转换为二叉搜索树	简单	反向使用中序性质，从升序序列构造平衡结构
230. 二叉搜索树中第 K 小的元素	中等	用正序中序计数定位名次，考察提前终止
783. 二叉搜索树节点最小距离	简单	需在中序中维护前驱值做差，共享变量含义不同
501. 二叉搜索树中的众数	简单	中序中统计连续相等段，共享状态是计数而非累加和
99. 恢复二叉搜索树	中等	借中序有序性找逆序对，修改的是两个节点的值