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

2026-03-28 HGNULB 约 4 分钟

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

分类

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

标签

深度优先搜索 树 二叉树 LCR 二叉搜索树

题目描述

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

题意分析

把二叉搜索树中每个节点的值，改为原树中所有大于等于它的节点值之和。只修改数值，保留原来的节点和连接关系，最后返回原根节点。

二叉搜索树的有序性决定了访问顺序：从大到小处理节点时，当前需要的那些更大值都已经访问过，可以用一个累计和直接求出新值。

解法：反中序累加

核心思路

[!blue]

二叉搜索树按“左、根、右”访问得到升序，改成“右、根、左”就得到降序。访问当前节点之前，所有原值比它大的节点都已处理，而更小的节点尚未处理。

用共享变量 s 保存已经访问的原节点值之和。到达当前节点时，先执行 s += root.val，再写入 root.val = s：加上当前原值之后，累计和恰好包含全部更大节点和当前节点，正是它的新值。

写回后继续处理左子树，它需要的累计范围还包括刚处理的当前节点。虽然右侧节点已经改值，但它们的原值早已计入 s，后续不会再次读取这些节点参与累加，所以原地修改不会污染计算。

s 的初值为 0，并在整次遍历中共享。Java 通过成员变量保存累计进度，Go 通过闭包保存；递归进入另一棵子树时，不能重新创建一个从 0 开始的累计和。

节点值可以为负，累计和不一定递增。正确性依赖的是降序访问覆盖了哪些原节点，而不是累计数值的变化方向。

解题步骤

1. 让累计和 s 从 0 开始，并由整次遍历共享。
2. 递归遇到空节点直接返回，不改变累计和。
3. 先处理右子树，再将当前原值加入 s，把 s 写回当前节点。
4. 最后处理左子树，继续使用已经更新的累计和。
5. 遍历完成后返回原根；空树会直接原样返回。

代码实现

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
}

复杂度分析

设节点数为 n，树高为 h。

• 时间复杂度：$O(n)$，每个节点只访问一次，进行一次累加与赋值。
• 空间复杂度：$O(h)$，来自递归栈；树退化成链时为 $O(n)$。

关键点总结

[!green]

• 反中序把更大值放在前面，让需要的总和变成一次顺序累加。
• 先使用节点原值，再写回累计和，已处理节点不再参与后续读取。
• 累计和贯穿整次遍历，不能按节点或子树重新开始计数。

易错点总结

[!yellow]

• 按普通中序累加：得到的是较小值的和，与题目方向相反。
• 先覆盖节点再累加：会丢失它的原值，导致后续累计错误。
• 在每层递归中重置累计和：会丢掉已经访问的更大节点信息。
• 假设累计和一定递增：负值节点可能使累计和减小，不能据此剪枝。

相似题目

题目	难度	关联与区别
230. 二叉搜索树中第 K 小的元素	中等	都利用BST中序有序性，本题改用逆中序累计更大值，原题按升序定位第k项。
897. 递增顺序搜索树	简单	同样通过有序遍历改造BST，原题改连接而保留节点值，本题改值并保留连接。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/24159387

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！