面试算法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;# 发…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...
项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...
浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...
使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)
macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 🍺 最新版brew安装慢到怀疑人生?别怕,教你轻松起飞! 最近Homebrew更新至最新版,每次执行 brew 命令时都会自动从官方地址 https://formulae.…...
深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向
在人工智能技术呈指数级发展的当下,大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性,吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型,成为释放其巨大潜力的关键所在&…...
人工智能 - 在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型
在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型。这些平台各有侧重,适用场景差异显著。下面我将从核心功能定位、典型应用场景、真实体验痛点、选型决策关键点进行拆解,并提供具体场景下的推荐方案。 一、核心功能定位速览 平台核心定位技术栈亮…...
