938. Range Sum of BST
2024-09-07 20:46:44
Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive).
The binary 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:
- The number of nodes in the tree is at most
10000. - The final answer is guaranteed to be less than
2^31.
Approach #1: C++. [recursive]
/**
* 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) {
ans = 0;
dfs(root, L, R);
return ans;
} private:
int ans; void dfs(TreeNode* root, int L, int R) {
if (root != NULL) {
if (L <= root->val && root->val <= R) {
ans += root->val;
}
if (L < root->val) {
dfs(root->left, L, R);
}
if (R > root->val) {
dfs(root->right, L, R);
}
}
}
};
Approach #2: Java. [Iterative]
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int rangeSumBST(TreeNode root, int L, int R) {
int ans = 0;
Stack<TreeNode> stack = new Stack();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node != null) {
if (L <= node.val && node.val <= R)
ans += node.val;
if (L < node.val)
stack.push(node.left);
if (R > node.val)
stack.push(node.right);
}
}
return ans;
}
}
Approach #3: Python.
# 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
"""
ans = 0
stack = [root]
while stack:
node = stack.pop()
if node:
if L <= node.val <= R:
ans += node.val
if L < node.val:
stack.append(node.left)
if R > node.val:
stack.append(node.right) return ans
最新文章
- ABP框架 - 多层结构
- Latex中画出函数文件的调用关系拓扑图
- [webgrid] – header - (How to Add custom html to Header in WebGrid)
- mysql的时间转化
- C# JSON字符串序列化与反序列化
- JS一些语法
- Subsequence
- Fatal error: Call to undefined function mysql_connect()
- Linux中命令行编译java接口总是提示找不到符号的疑难杂症的解决
- [Javascript] How to write a Javascript libarary
- Alter的用法（添加字段，删除字段，修改字段名）
- 有感于NC的强大
- hdu 2612 多终点BFS
- 20, CSS 定义选择器
- C#からネイティブDLLを呼び出す場合のVSからのデバッグのジレンマを解決する
- Noip数学整理
- OOP理解
- thinkphp 3.2.3 addAll方法的坑
- [BZOJ4444][SCOI2015]国旗计划(倍增)
- Gulp插件autoprefixer的使用