面试算法54:所有大于或等于节点的值之和
题目
给定一棵二叉搜索树,请将它的每个节点的值替换成树中大于或等于该节点值的所有节点值之和。假设二叉搜索树中节点的值唯一。例如,输入如图8.10(a)所示的二叉搜索树,由于有两个节点的值大于或等于6(即节点6和节点7),因此值为6节点的值替换成13,其他节点的值的替换过程与此类似,所有节点的值替换之后的结果如图8.10(b)所示。

分析
如果能够按照节点值从大到小按顺序遍历二叉搜索树,那么只需要遍历一次就够了,因为遍历到一个节点之前值大于该节点的值的所有节点已经遍历过。通常的中序遍历是先遍历左子树,再遍历根节点,最后遍历右子树,由于左子树节点的值较小,右子树节点的值较大,因此总体上就是按照节点的值从小到大遍历的。如果要按照节点的值从大到小遍历,那么只需要改变中序遍历的顺序,先遍历右子树,再遍历根节点,最后遍历左子树,这样遍历的顺序就颠倒过来了。
解
public class Test {public static void main(String[] args) {TreeNode node1 = new TreeNode(1);TreeNode node2 = new TreeNode(2);TreeNode node3 = new TreeNode(3);TreeNode node4 = new TreeNode(4);TreeNode node5 = new TreeNode(5);TreeNode node6 = new TreeNode(6);TreeNode node7 = new TreeNode(7);node4.left = node2;node4.right = node6;node2.left = node1;node2.right = node3;node6.left = node5;node6.right = node7;TreeNode result = convertBST(node4);System.out.println(result);}public static TreeNode convertBST(TreeNode root) {Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;int sum = 0;while (cur != null || !stack.isEmpty()) {while (cur != null) {stack.push(cur);cur = cur.right;}cur = stack.pop();sum += cur.val;cur.val = sum;cur = cur.left;}return root;}
}
相关文章:
面试算法54:所有大于或等于节点的值之和
题目 给定一棵二叉搜索树,请将它的每个节点的值替换成树中大于或等于该节点值的所有节点值之和。假设二叉搜索树中节点的值唯一。例如,输入如图8.10(a)所示的二叉搜索树,由于有两个节点的值大于或等于6(即…...
七月论文审稿GPT第二版:从Meta Nougat、GPT4审稿到LongLora版LLaMA、Mistral
前言 如此前这篇文章《学术论文GPT的源码解读与微调:从chatpaper、gpt_academic到七月论文审稿GPT》中的第三部分所述,对于论文的摘要/总结、对话、翻译、语法检查而言,市面上的学术论文GPT的效果虽暂未有多好,可至少还过得去&am…...
PyTorch入门学习(十二):神经网络-搭建小实战和Sequential的使用
目录 一、介绍 二、先决条件 三、代码解释 一、介绍 在深度学习领域,构建复杂的神经网络模型可能是一项艰巨的任务,尤其是当您有许多层和操作需要组织时。幸运的是,PyTorch提供了一个方便的工具,称为Sequential API,…...
Linux shell编程学习笔记20:case ... esac、continue 和break语句
一、case ... esac语句说明 在实际编程中,我们有时会请到多条件多分支选择的情况,用if…else语句来嵌套处理不烦琐,于是JavaScript等语言提供了多选择语句switch ... case。与此类似,Linux Shell脚本编程中提供了case...in...esa…...
树莓派4无法进入桌面模式(启动后出现彩色画面,然后一直黑屏,但是可以正常启动和ssh)
本文记录了这段比较坎坷的探索之路,由于你的问题不一定是我最终解决方案的,可能是前面探索路上试过的,所以建议按顺序看排除前置问题。 双十一又买了个树莓派 4B,插上之前树莓派 4B 的 TF 卡直接就能使用(毕竟是一样规…...
花草世界生存技能
多菌灵 杀菌常用 阿维菌素 杀虫常用 除蚜虫 吡虫啉 有毒性 内吸性(植物吸收) 苦参碱 无毒,中药提取 内吸性药 吡虫啉,噻虫嗪、啶虫脒、苦参碱 栀子花 春秋花后修剪 牡丹 秋冬种植; 洛阳产地; 肥料 …...
执行npm install时老是安装不成功node-sass的原因和解决方案
相信你安装前端项目所需要的依赖包(npm install 或 yarn install)时,有可能会出现如下报错: D:\code\**project > yarn install ... [4/4] Building fresh packages... [-/6] ⠁ waiting... [-/6] ⠂ waiting... [-/6] ⠂ wai…...
【MongoDB】集群搭建实战 | 副本集 Replica-Set | 分片集群 Shard-Cluster | 安全认证
文章目录 MongoDB 集群架构副本集主节点选举原则搭建副本集主节点从节点仲裁节点 连接节点添加副本从节点添加仲裁者节点删除节点 副本集读写操作副本集中的方法 分片集群分片集群架构目标第一个副本集第二个副本集配置集初始化副本集路由集添加分片开启分片集合分片删除分片 安…...
「Verilog学习笔记」四选一多路器
专栏前言 本专栏的内容主要是记录本人学习Verilog过程中的一些知识点,刷题网站用的是牛客网 分析 通过波形示意图我们可以发现,当sel为0,1,2时,输出mux_out分别为d3,d2,d1,那么sel3…...
asp.net 创建docker容器
首先创建asp.net web api 创建完成后如下图 添加docker支持 添加docker支持 添加linux docker支持...
Linux项目自动化构建工具-make/Makefile使用
make/Makefile使用介绍 make是一个命令makefile是一个在当前目录下存在的一个具有特定格式的文本文件 下面我们设计一个场景,实现make命令对我们code.c文件进行编译和删除。 1 #include<stdio.h> 2 3 int main() 4 { 5 printf("hello,world!…...
【React】03.脚手架的进阶应用
文章目录 暴露webpack配置暴露前后的区别config文件夹:scripts文件夹:package.json 常见的配置修改1.把sass改为less2.配置别名3.修改域名和端口号4.修改浏览器兼容5.处理Proxy跨域 2023年最新珠峰React全家桶【react基础-进阶-项目-源码-淘系-面试题】 …...
WPF开源控件HandyControl——零基础教程
学习Handycontrol的过程中,为后边快速开发,写的零基础教程,尽量看完就可以实践! 参考教程 中文文档:欢迎使用HandyControl | HandyOrg Github代码:https://github.com/HandyOrg/HandyControl 使用教程:WPF-HandyControl安装和使用 - 掘金 安装配置教程 创建wpf项目 …...
chinese-stable-diffusion中文场景文生图prompt测评集合
腾讯混元大模型文生图操作指南.dochttps://mp.weixin.qq.com/s/u0AGtpwm_LmgnDY7OQhKGg腾讯混元大模型再进化,文生图能力重磅上线,这里是一手实测腾讯混元的文生图在人像真实感、场景真实感上有比较明显的优势,同时,在中国风景、动…...
K-均值聚类算法
K-均值聚类算法是一种常用的无监督学习算法,目的是将一组数据点分为 K 个聚类。它的主要思想是通过迭代的方式不断调整聚类中心的位置,使得数据点与最近的聚类中心之间的距离最小。 算法步骤如下: 初始化 K 个聚类中心,可以随机…...
Xbox漫游指南
以Xbox series s为例 开机启动 用手柄连接,注意两颗电池要方向相反插入,虽然里面2个插槽长一样; Xbox APP极其难用,放弃,直接用手柄连接 转区 只需要一个空U盘,大小不限制,格式化为NTPS格式…...
降低毕业论文写作压力的终极指南
亲爱的同学们,时光荏苒,转眼间你们即将踏入毕业生的行列。毕业论文作为本科和研究生阶段的重要任务,不仅是对所学知识的综合运用,更是一次对自己学术能力和专业素养的全面考验。然而,论文写作常常伴随着压力和焦虑&…...
SELECT COUNT( * ) 与SELECT COUNT( 1 ) 区别
在 SQL 中,SELECT COUNT(*) 和 SELECT COUNT(1) 都用于统计符合条件的行数,但它们在具体实现和效率上有一些区别。 SELECT COUNT(*):这是一种常见且通用的写法,它会统计所有符合查询条件的行数,包括所有列,…...
[python 刷题] 1248 Count Number of Nice Subarrays
[python 刷题] 1248 Count Number of Nice Subarrays 题目如下: Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it. Return the number of nice sub-arrays. 这道题和 1343 Number of S…...
堆叠注入 [GYCTF2020]Blacklist1
打开题目 判断注入点 输入1,页面回显 输入1 页面报错 输入 1 # 页面正常,说明是单引号的字符型注入 我们输入1; show databases; # 说明有6个数据库 1; show tables; # 说明有三个表 我们直接查看FlagHere的表结构 1;desc FlagHere;# 发…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...
高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台
🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
