- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址:https://leetcode.com/contest/weekly-contest-110/problems/range-sum-of-bst/
Given the root
node of a binary search tree, return the sum of values of all nodes with value between L
and R
(inclusive).
Thebinary search tree is guaranteed to have unique values.
Example 1:
Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32
Example 2:
Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
Output: 23
Note:
1、 Thenumberofnodesinthetreeisatmost10000.;
2、 Thefinalanswerisguaranteedtobelessthan2^31.;
找出一个BST中,计算在[L,R]双闭区间内的所有节点的值的和。
看见BST,就想起来它特殊的性质。所以这个题肯定能用上性质。
如果root不存在,返回0。如果root节点在[L,R]内,那么把结果加上root的值,然后再分别加上左右子树的值。为什么?因为这个时候左右子树都可能存在满足[L,R]区间,所以必须都加上。
如果root的值比L还小,说明左子树一定不会满足[L,R]区间,那么直接向右边找就行。
如果root的值比R还大,说明右子树一定不会满足[L,R]区间,那么直接向左边找就行。
时间复杂度是O(N),空间复杂度是O(1)。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def rangeSumBST(self, root, L, R):
"""
:type root: TreeNode
:type L: int
:type R: int
:rtype: int
"""
if not root:
return 0
res = 0
if L <= root.val <= R:
res += root.val
res += self.rangeSumBST(root.left, L, R)
res += self.rangeSumBST(root.right, L, R)
elif root.val < L:
res += self.rangeSumBST(root.right, L, R)
elif root.val > R:
res += self.rangeSumBST(root.left, L, R)
return res
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
也可以直接判断寻找的方向,能简化一点代码。如果root节点小于R,说明右边可以继续搜索;如果root节点大于L,说明左边可以继续搜索。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def rangeSumBST(self, root, L, R):
"""
:type root: TreeNode
:type L: int
:type R: int
:rtype: int
"""
res = [0]
self.dfs(root, L, R, res)
return res[0]
def dfs(self, root, L, R, res):
if not root:
return
if L <= root.val <= R:
res[0] += root.val
if root.val < R:
self.dfs(root.right, L, R, res)
if root.val > L:
self.dfs(root.left, L, R, res)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
C++版本的代码如下:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int rangeSumBST(TreeNode* root, int L, int R) {
dfs(root, L, R);
return res;
}
private:
int res = 0;
void dfs(TreeNode* root, int L, int R) {
if (root == nullptr) return;
if (root->val <= R && root->val >= L) res += root->val;
if (root->val > L) dfs(root->left, L, R);
if (root->val < R) dfs(root->right, L, R);
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
我创建了以下 sub 来简单地说明问题。我将事件工作表的范围 A2:E10 分配给范围变量。然后,对于另一个范围变量,我将这个范围的子范围,单元格 (1, 1) 分配给 (3, 3)。 我原以为这将包
我使用正则表达式来搜索以下属性返回的纯文本: namespace Microsoft.Office.Interop.Word { public class Range {
我正在开发一个宏来突出显示某些行/单元格以供进一步审查。一些值/空白将以红色突出显示,其他以橙色突出显示,而整行应为黄色。我从上一个问题中得到了一些帮助,并添加了更多细节,它工作得几乎完美,但我被困在
这个问题在这里已经有了答案: What is the difference between range and xrange functions in Python 2.X? (28 个答案) 关闭
我在尝试运行脚本时遇到这个奇怪的错误,代码似乎是正确的,但似乎 python (3) 不喜欢这部分: def function(x): if int
我正在编写一种算法,将一些数据写入提供的输出范围(问题的初始文本包括具体细节,这将评论中的讨论转向了错误的方向)。我希望它在 API 中尽可能接近标准库中的其他范围算法。 我查看了 std::rang
这按预期工作: #include #include int main() { auto chunklist = ranges::views::ints(1, 13) | ranges::vie
我这里有一个字符串,我正在尝试对其进行子字符串化。 let desc = "Hello world. Hello World." var stringRange = 1..' 的值转换为预期的参数类型
我有一个高级搜索功能,可以根据日期和时间查询记录。我想返回日期时间范围内的所有记录,然后从该范围内返回我想将结果缩小到一个小时范围(例如 2012 年 5 月 1 日 - 2012 年 5 月 7 日
Go 中的 range 函数和 range 关键字有什么区别? func main(){ s := []int{10, 20, 30, 40, 50, 60, 70, 80, 90}
如果我有一个范围,如何将其拆分为一系列连续的子范围,其中指定了子范围(存储桶)的数量?如果没有足够的元素,则应省略空桶。 例如: splitRange(1 to 6, 3) == Seq(Range(
我正在开发 VSTO Excel 项目,但在管理 Range 对象时遇到一些问题。 实际上,我需要知道当前选定的范围是否与我存储在列表中的另一个范围重叠。所以基本上,我有 2 个 Range 实例,我
在即将推出的 C++20 系列中,将有 range concept具有以下定义: template concept range = __RangeImpl; // exposition-only de
希望有人能回答我的问题。我在 VHDL 代码中遇到了这个命令,但不确定它到底做了什么。有人可以澄清以下内容吗? if ( element1 = (element1'range => '0')) the
可以将范围嵌套在范围中吗?使用范围内的变量?因为我想取得一些效果。为了说明这个问题,我有以下伪代码: for i in range(str(2**i) for i in range(1,2)):
我想在 2 个日期之间创建一个范围,并且我的范围字段有时间 damage_list = Damage.objects.filter(entry_date__range=(fdate, tdate))
在下面的代码中 #include #include #include int main() { std::unordered_mapm; m["1"]=1; m["2"]=2
我试图为我的电子表格做一个简单的循环,它循环遍历一个范围并检查该行是否为空,如果不是,则循环遍历一系列列并检查它们是否为空,如果是则它设置一个消息。 问题是每次它通过循环 ro.value 和 col
我在将一个工作簿范围中的值分配给当前工作簿中的某个范围时遇到问题。当我使用 Range("A1:C1") 分配我的范围时,此代码工作正常,但是当我使用 Range(Cells(1,1),Cells(1
我改写了原来的问题。 Sub s() Dim r As Range Set r = ActiveSheet.Range("B2:D5") Debug.Print r.Rows.Count
我是一名优秀的程序员,十分优秀!