难度中等854收藏分享切换为英文接收动态反馈
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
- 节点的左子树仅包含键 小于 节点键的节点。
- 节点的右子树仅包含键 大于 节点键的节点。
- 左右子树也必须是二叉搜索树。
**注意：**本题和 1038: https://leetcode-cn.com/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之间。 - 树中的所有值 互不相同 。
- 给定的树为二叉搜索树。
递归
这道题其实不难，因为是二叉搜索树，它中序遍历的特性就是从小到大排序的，那么我们要求的是那些比节点值大或者等于的节点累加的和，那不就是相对于是一个数组比如说 [1, 2, 3, 4, 5] 这样子，最后变成了 [15, 14, 12, 9, 5]，我们只需要用一个变量 sum 来记录这个前缀和，并且我们从后往前遍历累加这个 sum 变量，就能得到这样子的序列。
因此，我们只需要将原来的有序序列的顺序为左中右，变成右中左遍历，就能从后往前遍历来获取前缀和，并且累加上去！
class Solution {
public:
void _convert(TreeNode* root, int& sum)
{
if(root == nullptr)
return;
// 中序遍历
_convert(root->right, sum);
// 前缀和累加，并且更新当前的节点值
sum += root->val;
root->val = sum;
_convert(root->left, sum);
}
TreeNode* convertBST(TreeNode* root) {
int sum = 0;
_convert(root, sum);
return root;
}
};