上海
奇葩年年有，今年特别多，最近一网友本来打算第二天入职的，结果被通知不用去了，有需求在过去，这明显是被放鸽子了。如果不想要可以提前说，别人也可以继续找，不要等到快入职的时候别人问了才说。网友建议：狠狠骂他，毁offer都这么理直气壮。
网友回复：
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第538题：把二叉搜索树转换为累加树
问题描述
来源：LeetCode第538题
难度：中等
给出 二叉搜索树 的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
示例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]
树中的节点数介于 0 和 10^4 之间。
每个节点的值介于 -10^4 和 10^4 之间。
树中的所有值 互不相同 。
给定的树为二叉搜索树。
问题分析
这题是让把二叉搜索树中每个节点的值改成所有大于等于该节点值的和，考察的也是二叉搜索树的特性。
如果这题换一种说法，把一个 有序数组 中每个元素变成所有大于等于它的元素和，我们只需要从后往前遍历数组然后累加即可，因为有序数组中每一个元素后面的值都是大于它的。
但这里是一棵二叉搜索树， 二叉搜索树的一个重要特性就是它的中序遍历结果是有序的 ，我们只需要把中序遍历反过来，也就是 先遍历右子树，在访问当前节点，最后在遍历左子树 ，这样就相当于二叉树中所有的节点从大往小的顺序访问，这个时候就可以参考有序数组的操作了。
JAVA：
int sum = 0;// 累加值
public TreeNode convertBST(TreeNode root) {
if (root == null)
return null;
convertBST(root.right);// 递归右子树
sum += root.val;
root.val = sum;
convertBST(root.left);// 递归左子树
return root;
}C++：
public:
int sum = 0;// 累加值
TreeNode *convertBST(TreeNode *root) {
if (root == nullptr)
return nullptr;
convertBST(root->right);// 递归右子树
sum += root->val;
root->val = sum;
convertBST(root->left);// 递归左子树
return root;
}Python：
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
s = 0 # 累加值
def dfs(node):
if not node:
return node
dfs(node.right) # 递归右子树
nonlocal s
s += node.val
node.val = s
dfs(node.left) # 递归左子树
return node
dfs(root)
return root笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
