【Leetcode】938. 二叉搜索树的范围和

文章目录

  • 题目
  • 思路
  • 代码
  • 结论

题目

题目链接
给定二叉搜索树的根结点 root,返回值位于范围 [low, high] 之间的所有结点的值的和。

示例 1:
在这里插入图片描述
输入:root = [10,5,15,3,7,null,18], low = 7, high = 15
输出:32

示例 2:
在这里插入图片描述
输入:root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
输出:23

提示:

  • 树中节点数目在范围 [1, 2 * 104] 内
  • 1 <= Node.val <= 105
  • 1 <= low <= high <= 105
  • 所有 Node.val 互不相同

思路

按深度优先搜索的顺序计算范围和。记当前子树根节点为 root,分以下四种情况讨论:

  1. 当根节点为空时,应直接返回0。
  2. 若根节点的值大于high,因为二叉搜索树右子树上的所有节点值均大于根节点的值,故只需考虑左子树的范围和。
  3. 若根节点的值小于low,因为二叉搜索树左子树上的所有节点值均小于根节点的值,故只需考虑右子树的范围和。
  4. 当根节点的值在[low, high]范围内时,应返回根节点的值、左子树的范围和、右子树的范围和的总和。

此时应返回 root 节点的值、左子树的范围和、右子树的范围和这三者之和。

代码

class Solution {
public:int rangeSumBST(TreeNode* root, int low, int high) {int ans=0;if(root==nullptr)return 0;if(root->val > high)return rangeSumBST(root->left,low,high);else if(root->val < low)return rangeSumBST(root->right,low,high);else return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);}
};

结论

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/266878.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Spring的优点

1.方便解耦&#xff0c;简化开发 Spring就是一个容器&#xff0c;可以将所有对象创建和关系维护交给Spring管理。 2.AOP编程支持 面向切面编程&#xff0c;方便实现程序进行权限拦截&#xff0c;运行监控等功能。 3.声明式事务的支持 通过配置完成事务的管理&#xff0c;…

kotlin单例模式,4年小Android的心路历程

一、Java基础 我知道大家一定有很久都没有注意到这个点了&#xff0c;平时的工作应该也很少涉及到这些底层知识吧&#xff0c;但是这些东西很重要。如果是想要跳槽加薪或者是应对即将到来的面试&#xff0c;这些都是不可忽视的知识。 在这一点里&#xff0c;需要重视的点有&am…

【ArcGIS】基本概念-空间参考与变换

ArcGIS基本概念-空间参考与变换 1 空间参考与地图投影1.1 空间参考1.2 大地坐标系&#xff08;地理坐标系&#xff09;1.3 投影坐标系总结 2 投影变换预处理2.1 定义投影2.2 转换自定义地理&#xff08;坐标&#xff09;变换2.3 转换坐标记法 3 投影变换3.1 矢量数据的投影变换…

零基础学编程,中文编程工具之进度标尺构件的编程用法

零基础学编程&#xff0c;中文编程工具之进度标尺构件的编程用法 一、前言 今天给大家分享的中文编程开发语言工具 进度条构件的用法。 编程入门视频教程链接 https://edu.csdn.net/course/detail/39036 编程工具及实例源码文件下载可以点击最下方官网卡片——软件下载——…

基于深度学习的故障诊断入门学习路线—课程目录介绍

1、基于深度学习的故障诊断入门学习路线—课程目录介绍 2、口碑与评价&#xff1a; 2.1 来自某985硕士研究生 2.2 阳阳同学 2.3 小杰同学 2.4 2024.02.25直播课 3、欢迎大家跟着诊断之家老哥一起学习

CentOS安装GUI图形界面

CentOS安装图形界面 CentOS minimal环境安装图形界面。 列出所有可用的Environment Groups yum group list yum groupinfo "GNOME Desktop"选择GNOME Desktop软件包组进行安装 yum groupinstall -y GNOME Desktop1 如果要通过GUI配置网络需要安装Server with GU…

k8s-helm部署应用 19

Helm部署nfs-client-provisioner&#xff08;存储类&#xff09;&#xff1a; 预先配置好外部的NFS服务器 部署 Helm部署nginx-ingress应用&#xff1a; 添加下载ingress 拉取 解开并修改 部署 测试 回收 helm部署metrics-server&#xff1a; 清除之前的metrics部署 下载…

C语言标准库函数qsort( )——数据排序

大家好&#xff01;我是保护小周ღ&#xff0c;本期为大家带来的是深度解剖C语言标准库函数 qsort()&#xff0c;qsort()函数他可以对任意类型的数据排序&#xff0c;博主会详细解释函数使用方法&#xff0c;以及使用快速排序的左右指针法模拟实现函数功能&#xff0c;这样的排…

Docker(运维工具)—— 学习笔记

快速构建、运行、管理应用的工具 一、安装docker 参考Install Docker Engine on Ubuntu | Docker Docs 二、快速入门 1、镜像和容器 docker镜像可以做到忽略操作系统的差异&#xff0c;跨平台运行&#xff0c;忽略安装的差异 当我们利用Docker安装应用时&#xff0c;Dock…

unity shaderGraph实例-物体线框显示

文章目录 本项目基于URP实现一&#xff0c;读取UV网格&#xff0c;由自定义shader实现效果优缺点效果展示模型准备整体结构各区域内容区域1区域2区域3区域4shader属性颜色属性材质属性后处理 实现二&#xff0c;直接使用纹理&#xff0c;使用默认shader实现优缺点贴图准备材质准…

C++——友元

目录 友元 友元函数 友元函数使用案例 友元类 友元 友元是C提供的一种突破封装&#xff08;突破类域&#xff09;的方式&#xff0c;有时提供了便利。但是友元会增加耦合度&#xff0c;但破坏了封装&#xff0c;所以友元不宜多用。友元分为友元函数和友元类。 友元函数 友元…

仿牛客网项目---帖子详情功能的实现

这篇文章主要讲讲帖子详情功能。其实帖子详情功能简单来说就是你点进去可以看到文章&#xff0c;这就叫帖子详情功能。那接下来我讲讲我的这个项目是如何实现这个功能的。 首先写DAO层。 Mapper public interface DiscussPostMapper {List<DiscussPost> selectDiscussPo…

数据结构之二叉树的精讲

&#x1d649;&#x1d65e;&#x1d658;&#x1d65a;!!&#x1f44f;&#x1f3fb;‧✧̣̥̇‧✦&#x1f44f;&#x1f3fb;‧✧̣̥̇‧✦ &#x1f44f;&#x1f3fb;‧✧̣̥̇:Solitary_walk ⸝⋆ ━━━┓ - 个性标签 - &#xff1a;来于“云”的“羽球人”。…

网络编程学习

思维导图 代码练习 TCP实现通信 服务器端代码 #include <myhead.h> #define SER_IP "192.168.152.135" #define SER_PORT 8910 int main(int argc, const char *argv[]) {//&#xff11;创建用于监听的套接字int sfd -1;sfd socket(AF_INET,SOCK_STREAM,0)…

【刷题】Leetcode 1609.奇偶树

Leetcode 1609.奇偶树 题目描述广度优先搜索&#xff08;BFS&#xff09;深度优先算法&#xff08;DFS&#xff09; 思路一&#xff08;BFS&#xff09;思路二&#xff08;DFS&#xff09;Thanks♪(&#xff65;ω&#xff65;)&#xff89;谢谢阅读&#xff01;&#xff01;&a…

网络爬虫的危害,如何有效的防止非法利用

近年来&#xff0c;不法分子利用“爬虫”软件收集公民隐私数据案件屡见不鲜。2023年8月23日&#xff0c;北京市高级人民法院召开北京法院侵犯公民个人信息犯罪案件审判情况新闻通报会&#xff0c;通报侵犯公民个人隐私信息案件审判情况&#xff0c;并发布典型案例。在这些典型案…

FMM 笔记:st-matching(colab上执行)【官方案例解读】

在colab上运行&#xff0c;所以如何在colab上安装fmm&#xff0c;可见FMM 笔记&#xff1a;在colab上执行FMM-CSDN博客 st-matching见论文笔记&#xff1a;Map-Matching for low-sampling-rate GPS trajectories&#xff08;ST-matching&#xff09;-CSDN博客 0 导入库 from…

【vuex之五大核心概念】

vuex:五大核心概念 一、state状态1.state的含义2.如何访问以及使用仓库的数据&#xff08;1&#xff09;通过store直接访问获取store对象 &#xff08;2&#xff09;通过辅助函数MapState 二、mutations1.作用2.严格模式3.操作流程定义 mutations 对象&#xff0c;对象中存放修…

Parquet 文件生成和读取

文章目录 一、什么是 Parquet二、实现 Java 读写 Parquet 的流程方式一&#xff1a;遇到的坑&#xff1a;坑1&#xff1a;ClassNotFoundException: com.fasterxml.jackson.annotation.JsonMerge坑2&#xff1a;No FileSystem for scheme "file"坑3&#xff1a;与 spa…

第四十三天| 1049. 最后一块石头的重量 II、494. 目标和、474.一和零

01背包问题 Leetcode 1049. 最后一块石头的重量 II 题目链接&#xff1a;1049 最后一块石头的重量 II 题干&#xff1a;有一堆石头&#xff0c;用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合&#xff0c;从中选出任意两块石头&#xff0c;然后将…