LeetCode 0938.二叉搜索树的范围和:深度优先搜索(可中序遍历)

news/2024/4/17 6:42:53

【LetMeFly】938.二叉搜索树的范围和:深度优先搜索(可中序遍历)

力扣题目链接:https://leetcode.cn/problems/range-sum-of-bst/

给定二叉搜索树的根结点 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 互不相同

方法一:深度优先搜索(可中序遍历)

二叉搜索树有一个性质:其中序遍历得到的序列递增。

但其实我们不使用这个性质也可以,只需要将其当作一个普通的二叉树。

遍历二叉树(可以中序也可以其他)并且在遍历途中判断当前节点的值是否在[low, high]之间。如果是则累加之。

  • 时间复杂度 O ( N ) O(N) O(N),其中 N N N是二叉树节点的个数
  • 空间复杂度 O ( N ) O(N) O(N)

AC代码

C++
class Solution {  // AC,96.46%,73.98%
private:int ans;void dfs(TreeNode* root, int l, int r) {if (!root) {return;}dfs(root->left, l, r);if (root->val >= l && root->val <= r) {ans += root->val;}dfs(root->right, l, r);}
public:int rangeSumBST(TreeNode* root, int low, int high) {ans = 0;dfs(root, low, high);return ans;}
};
Python
# from typing import Optional# # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = rightclass Solution:def dfs(self, root: Optional[TreeNode], l: int, r: int) -> None:if not root:returnself.dfs(root.left, l, r)if l <= root.val <= r:self.ans += root.valself.dfs(root.right, l, r)def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:self.ans = 0self.dfs(root, low, high)return self.ans

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/136306565


https://www.xjx100.cn/news/3293471.html

相关文章

YOLOv9-Openvino和ONNXRuntime推理【CPU】

1 环境&#xff1a; CPU&#xff1a;i5-12500 Python&#xff1a;3.8.18 2 安装Openvino和ONNXRuntime 2.1 Openvino简介 Openvino是由Intel开发的专门用于优化和部署人工智能推理的半开源的工具包&#xff0c;主要用于对深度推理做优化。 Openvino内部集成了Opencv、Tens…

数据分析Pandas专栏---第九章<Pandas数据筛选和过滤(1)>

前言: Pandas数据筛选和过滤在数据分析和处理中起着至关重要的作用。无论是清理数据、提取有效信息&#xff0c;还是进行统计分析&#xff0c;有效地筛选和过滤数据是关键步骤之一。 通过数据筛选&#xff0c;我们可以根据特定条件选择感兴趣的数据子集&#xff0c;并排除不相…

ubuntu常见配置

ubuntu各个版本的安装过程大差小不差&#xff0c;可以参考&#xff0c;ubuntu20.04 其它版本换一下镜像版本即可 安装之后需要配置基本的环境&#xff0c;我的话大概就以下内容&#xff0c;后续可能有所删改 sudo apt-get update sudo apt-get install gcc sudo apt-get inst…

这才是最适合普通人的短视频矩阵玩法

​牛丸哥&#xff0c;虽然他的内容平平无奇&#xff0c;直播间也就只有几十个人&#xff0c;但他就靠火力覆盖打法卖牛肉丸&#xff0c;卖了150万单&#xff01;你猜他之前发了多少条作品&#xff1f;15万条&#xff0c;全是流水线的内容&#xff0c;而且都有几十上百的点赞&am…

省市区街道/乡镇四级联动vue3

最近优化了一个省.市.区/县、乡镇/街道的四级联动组件&#xff0c;技术栈是element vue3记录一下。 本来是这样的三级联动&#xff1a; 这个三级联动很简单&#xff0c;直接利用el-select组件把地区值带进去就行了&#xff0c;现在要优化成省.市.区/县、乡镇/街道的四级联动&…

抖音上货API订单API:自动化上架商品批量获取商品详情信息

随着移动互联网的迅猛发展&#xff0c;短视频平台逐渐成为了全球用户的新宠。在中国&#xff0c;抖音作为一款短视频分享应用&#xff0c;凭借其独特的内容形式和创新的社交模式&#xff0c;迅速俘获了亿万用户的心。为了满足不断增长的用户需求和开发者社区的创新需求&#xf…

本地快速部署谷歌开放模型Gemma教程(基于LMStudio)

本地快速部署谷歌开放模型Gemma教程&#xff08;基于LMStudio&#xff09; 一、介绍 Gemma二、部署 Gemma2.1 部署工具2.1 部署步骤 三、总结 一、介绍 Gemma Gemma是一系列轻量级、最先进的开放式模型&#xff0c;采用与创建Gemini模型相同的研究和技术而构建。可以直接运行在…

前端使用类和方法封装的区别

在前端开发中&#xff0c;使用类和方法封装都是常见的方式来组织和管理代码。它们之间的主要区别在于&#xff1a; 类封装&#xff1a; 面向对象&#xff1a;类是面向对象编程的核心概念&#xff0c;通过类可以创建对象&#xff0c;对象可以包含属性和方法。封装性&#xff1a;…