毁offer还这么理直气壮。。。

猿大侠 · 公众号 · · 2024-07-29 12:08

正文

奇葩年年有，今年特别多，最近一网友本来打算第二天入职的，结果被通知不用去了，有需求在过去，这明显是被放鸽子了。如果不想要可以提前说，别人也可以继续找，不要等到快入职的时候别人问了才说。网友建议：狠狠骂他，毁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]

问题分析

这题是让把二叉搜索树中每个节点的值改成所有大于等于该节点值的和，考察的也是二叉搜索树的特性。

如果这题换一种说法，把一个有序数组中每个元素变成所有大于等于它的元素和，我们只需要从后往前遍历数组然后累加即可，因为有序数组中每一个元素后面的值都是大于它的。

但这里是一棵二叉搜索树，二叉搜索树的一个重要特性就是它的中序遍历结果是有序的，我们只需要把中序遍历反过来，也就是先遍历右子树，在访问当前节点，最后在遍历左子树，这样就相当于二叉树中所有的节点从大往小的顺序访问，这个时候就可以参考有序数组的操作了。

JAVA：

int sum = 0;// 累加值

public TreeNode convertBST(TreeNode root) {
    if (root == null)
        return null;
    convertBST(root.right);// 递归右子树

推荐文章

Quora文选英语 · 老外说𝒎𝒖𝒎'𝒔 𝒕𝒉𝒆 𝒘𝒐𝒓𝒅，可不是【妈妈的话】！到底是啥意思？

昨天

知乎日报 · 有什么东西是外国人吃，而中国人不吃的？

2 天前

知乎日报 · 世界上第一个养猫的人是谁？

2 天前

巴比特资讯 · 杨植麟和梁文锋，论文撞车了

2 天前

巴比特资讯 · 第一批DeepSeek开发者，已经开始逃离了

2 天前

21世纪经济报道 · 献给所有妈妈，这些真实、动人的影像有着你们共同的身影

8 年前

车早茶 · 老司机告诉你，选车看好这5个问题就够了！

7 年前

Parke更好家 · Parke | 喜欢在杭州当地王的融信，遇到了一次品牌危机

7 年前

扑克投资家 · 宏观大周期、黑色供给侧、农业调结构：一网打尽中国期货分析师论坛精华合集

7 年前

V先生专栏 · 你的人缘，价值百万！

7 年前