树与图中等1 种解法
#538把二叉搜索树转换为累加树
把每个节点值改为原树中大于等于该值的所有节点值之和。
#二叉搜索树#反向中序遍历
原题
给出二叉 搜索 树的根节点 root，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），将其转换为一个更大的树，使得原始二叉搜索树中的每个节点值都变为原本值加上原本二叉搜索树中所有比该节点值大的节点值的总和。
提醒一下，二叉搜索树满足下列约束条件：
- 节点的左子树仅包含键 小于 节点键的节点。
- 节点的右子树仅包含键 大于 节点键的节点。
- 左右子树也必须是二叉搜索树。
注意：本题和 1038: https://leetcode.cn/problems/binary-search-tree-to-greater-sum-tree/ 相同
示例 1：
输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] 输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2：
输入：root = [0,null,1] 输出：[1,null,1]
示例 3：
输入：root = [1,0,2] 输出：[3,3,2]
示例 4：
输入：root = [3,2,4,1] 输出：[7,9,4,10]
提示：
- 树中的节点数介于
0和104之间。 - 每个节点的值介于
-104和104之间。 - 树中的所有值 互不相同 。
- 给定的树为二叉搜索树。
解题主线
- 右—根—左是 BST 的降序遍历，可维护已访问较大值的前缀和。
解法 1：反向中序累加
递归函数返回处理完子树后的累计和，不依赖实例字段。
-
时间复杂度： O(n)
-
空间复杂度： O(h)
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class Solution {
public TreeNode convertBST(TreeNode root) {
accumulate(root, 0);
return root;
}
private int accumulate(TreeNode node, int sum) {
if (node == null) return sum;
// 反向中序先处理更大值，返回时 sum 已包含整个右子树
sum = accumulate(node.right, sum);
// 此时累计值恰为所有大于等于当前节点的原始值之和
sum += node.val;
node.val = sum;
// 将更新后的累计和继续传给值更小的左子树
return accumulate(node.left, sum);
}
}边界与易错点
- 累加和应沿右子树返回后更新根，再传给左子树。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/tree/Q538_convertBST.java