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

2024-04-29 HGNULB 约 8 分钟

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

分类

题目描述

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

题意分析

给一棵二叉搜索树，要把每个节点的值改成「它自己的原值，加上原树中所有比它大的节点值之和」，树的形状保持不变，最后返回同一个根。

第一个约束信号是「二叉搜索树」而非普通二叉树。这意味着节点值之间有全序关系，并且这个关系已经被树的结构编码好了：任意节点的左子树全部更小、右子树全部更大。所以「比某个节点大的那些节点」不是散落在树里的任意集合，而是可以顺着结构定位的一段。

第二个信号是所有节点值互不相同，因此「大于它的值之和」和「大于等于它的值之和」是同一个数，不需要为相等的情况纠结。

第三个信号是要求原地改值并返回原根，不是构造新树。所以整个过程只写 val，不动 left 和 right。

边界要想清楚三处：空树直接返回空；单节点树的新值就等于原值（没有更大的节点）；节点值可能为负，累加过程中的 sum 未必单调，但这不影响算法本身。

解法：反向中序遍历累加

核心思路

最朴素的想法是对每个节点单独求答案：遍历整棵树，把所有大于它的值加起来。这是对的，但每个节点都要扫一遍全树，总代价 $O(n^2)$。瓶颈非常明显——不同节点求的那些「更大值之和」高度重叠，却被反复重算。

换个角度：如果能按某个顺序依次访问节点，让「比当前节点大的所有节点」恰好是「已经访问过的节点」，那么只要维护一个运行中的累加值，每个节点的答案就是常数时间得到的。

这样的顺序存在吗？二叉搜索树的中序遍历（左、根、右）给出的是从小到大的序列。把它整个倒过来，也就是按右、根、左的顺序走，得到的就是从大到小的序列。在这个顺序下，访问到某个节点时，所有比它大的节点都已经走过了，一个不多、一个不少。

不变量是：在反向中序遍历中，每次即将处理节点 node 之前，sum 恰好等于原树中所有严格大于 node.val 的节点值之和。 于是先执行 sum += node.val，此刻 sum 就变成了「大于等于 node.val 的所有值之和」，也正是 node 的新值，直接赋回去即可。随后进入左子树时，左子树里的每个节点都小于 node，而更新后的 sum 已经把 node 计入，不变量继续成立。

这里有个容易忽略的细节：sum += node.val 用的必须是原值。因为赋值语句写在累加之后，读到的确实是尚未被覆盖的原值，顺序不能颠倒。

解题步骤

准备一个跨递归共享的 sum 并初始化为 0。Java 版用成员变量并在入口重置，Go 版用闭包捕获局部变量；关键是它必须在整棵树的遍历过程中持续累积，不能随递归层级被复制。

递归到空节点直接返回。空子树对累加没有任何贡献，这条出口同时兼顾了空树输入。

先递归右子树。这是整个解法的核心一步：右子树里的所有值都比当前节点大，必须在当前节点之前被计入 sum。

回到当前节点，执行 sum += node.val，再执行 node.val = sum。两句的先后顺序决定了新值是否包含节点自身；先累加再赋值，正好实现「原值加上所有更大值」。

最后递归左子树。左子树里的值都比当前节点小，它们的答案必须包含当前节点，所以必须晚于上一步执行。

遍历结束后返回原 root。树的结构从头到尾没被修改，根引用依然有效。

以 [4,1,6,0,2,5,7] 走一遍：这棵树的根是 4，左子树根 1（左孩子 0、右孩子 2），右子树根 6（左孩子 5、右孩子 7）。初始 sum = 0。递归从 4 进入，先钻右子树到 6，再钻到 7；7 的右孩子为空，返回。处理 7：sum = 0 + 7 = 7，7.val 改成 7；左孩子为空。回到 6：sum = 7 + 6 = 13，6.val 改成 13；进入左孩子 5，其右孩子为空，处理 5：sum = 13 + 5 = 18，5.val 改成 18，左孩子为空。回到根 4：sum = 18 + 4 = 22，4.val 改成 22。接着进入左子树 1，先走它的右孩子 2；2 的右孩子为空，处理 2：sum = 22 + 2 = 24，2.val 改成 24，左孩子为空。回到 1：sum = 24 + 1 = 25，1.val 改成 25；进入左孩子 0，右孩子为空，处理 0：sum = 25 + 0 = 25，0.val 改成 25，左孩子为空。遍历结束，各节点新值为 4 → 22、1 → 25、6 → 13、0 → 25、2 → 24、5 → 18、7 → 7，逐一核对：比 5 大的是 6 和 7，5 + 6 + 7 = 18 正确；比 2 大的是 4、5、6、7，2 + 4 + 5 + 6 + 7 = 24 正确。

代码实现

class Solution {
    private int sum;

    public TreeNode convertBST(TreeNode root) {
        sum = 0;
        dfs(root);
        return root;
    }

    private void dfs(TreeNode node) {
        if (node == null) {
            return;
        }

        dfs(node.right);

        // sum 保存所有已经访问过的更大节点之和。
        sum += node.val;
        node.val = sum;

        dfs(node.left);
    }
}

func convertBST(root *TreeNode) *TreeNode {
    sum := 0

    var dfs func(node *TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }

        dfs(node.Right)

        // sum 保存所有已经访问过的更大节点之和。
        sum += node.Val
        node.Val = sum

        dfs(node.Left)
    }

    dfs(root)
    return root
}

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是节点数。每个节点进入递归一次，在那一次里只做一次加法和一次赋值，没有任何重复扫描。

空间复杂度：$O(h)$，其中 $h$ 是树高，全部来自递归调用栈；本题不保证树平衡，退化成链时为 $O(n)$，平衡时为 $O(\log n)$。

关键点总结

遇到二叉搜索树，先问「我需要的顺序是什么」。升序用中序，降序用反向中序，把遍历方向当成可调参数，能省掉大量额外排序或查找。

「每个元素依赖它之后所有元素的聚合值」这一类需求，通用解法是倒着扫并维护后缀累积量。本题只是把线性数组换成了树，本质仍是后缀和。

累加与赋值的先后顺序编码了「包不包含自己」这一语义差别，写代码前先把它想清楚，比写完再试更可靠。

共享状态要放在整棵树的作用域里，不能作为递归参数按值传递，否则左右子树各自持有一份拷贝，累积链条会断。

面试视角：主动说出 $O(n^2)$ 的逐点求和法并指出其重复计算，再给出反向中序的 $O(n)$ 解，能展示从暴力到优化的完整推理，而不是背模板。

面试视角：常见追问有两个。一是「递归改迭代」，答用显式栈按右、根、左压栈即可；二是「能否 $O(1)$ 空间」，答可以用 Morris 遍历的反向版本，靠临时线索指针替代栈，但实现复杂度高，通常只需说清思路。

易错点总结

错误写法：按普通中序（左、根、右）遍历并累加。用例 [4,1,6,0,2,5,7] → 访问 0 时 sum 为 0，它会被改成 0 而不是正确的 25，整棵树累加方向完全反了。

错误写法：把 sum += node.val 和 node.val = sum 写反顺序，即先赋值再累加。用例 [0,null,1] → 节点 1 会被赋成 0，然后 sum 累加的是已被覆盖的值，结果既漏了自身又污染了后续累积。

错误写法：把 sum 作为递归参数按值传入。用例 [4,1,6,0,2,5,7] → 右子树累积出的 18 无法传回上层，节点 4 只会加到自己，左子树全部算错。

错误写法：在 dfs 内部重新初始化 sum = 0。用例任意多层树 → 每次进入递归都清零，最终每个节点的新值都等于自己的原值，转换等于没做。

错误写法：递归左右子树的顺序写对了，但把节点处理放在两次递归之后（后序位置）。用例 [4,1,6,0,2,5,7] → 处理 4 时左子树已经先跑过，sum 里混进了比 4 小的值，4 会被算成 22 之外的错误值。

错误写法：返回 null 或返回新建的树根。用例 [0,null,1] → 调用方拿不到被修改的原树，判题直接失败；本题要求原地修改并返回原根。

错误写法：假设节点值全为正，用「sum 单调递增」来做提前剪枝。用例 [0,-4,1] → 累加过程中 sum 会下降，任何基于单调性的剪枝都会误裁分支。

错误写法：先把中序序列存进数组、算出后缀和，再第二次遍历回填，但回填时用的是升序而非降序对应关系。用例 [4,1,6,0,2,5,7] → 下标对应错位，节点 0 拿到了本属于 7 的后缀和，全树数值张冠李戴。

错误写法：递归出口漏写空节点判断，改为在调用前检查 node.right != null 却漏了 node.left != null。用例 [1,null,2] → 进入左孩子时解引用空指针，直接崩溃。

相似题目

题目	难度	考察点
1038. 从二叉搜索树到更大和树	中等	与本题同解，仅题面表述不同，可用作即时复盘
LCR 054. 把二叉搜索树转换为累加树	中等	同一模型的国内版编号，适合检验模板是否稳定
98. 验证二叉搜索树	中等	中序序列必须严格递增，需要维护前驱值比较
230. 二叉搜索树中第 K 小的元素	中等	正向中序计数并提前终止，考察剪枝时机
剑指 Offer 54. 二叉搜索树的第k大节点	简单	同为反向中序，但计数到第 `k` 个即可返回
897. 递增顺序搜索树	简单	中序过程中重接指针，把树拉直成只有右孩子的链
LCR 052. 递增顺序搜索树	简单	同上题模型，可对比不同判题下的返回约定
426. 将二叉搜索树转化为排序的双向链表	中等	中序中维护前驱节点并双向连接，最后首尾成环
剑指 Offer 36. 二叉搜索树与双向链表	中等	与上题同构，考察对原地改指针的熟练度
面试题 04.05. 合法二叉搜索树	中等	判定有效性时需处理重复值与整型极值边界
面试题 17.12. BiNode	简单	要求就地转换且左指针必须置空，考察细节收尾