目录
难度简单
给定二叉搜索树的根结点 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 <= 1051 <= low <= high <= 105- 所有
Node.val互不相同
方法一：深度优先搜索
c++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
//深度优先搜索，以根节点的值分为四种情况
class Solution {
public:
int rangeSumBST(TreeNode* root, int low, int high) {
if(root==nullptr) return 0;
if (root->val > high) return (rangeSumBST(root->left,low,high));
if(root->val<low) return (rangeSumBST(root->right,low,high));
// low<root<high 的情况
return root->val+rangeSumBST(root->left,low,high)+rangeSumBST(root->right,low,high);
}
};
python
# 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 = right
class Solution:
def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
if not root:
return 0
if root.val>high:
return self.rangeSumBST(root.left,low,high)
if root.val<low:
return self.rangeSumBST(root.right,low,high)
return root.val+self.rangeSumBST(root.left,low,high) +self.rangeSumBST(root.right,low,high)复杂度分析
-
时间复杂度：O(n)O(n)，其中 nn 是二叉搜索树的节点数。
-
空间复杂度：O(n)O(n)。空间复杂度主要取决于栈空间的开销。
方法二：广度优先搜索
使用广度优先搜索的方法，用一个队列 qq 存储需要计算的节点。每次取出队首节点时，若节点为空则跳过该节点，否则按方法一中给出的大小关系来决定加入队列的子节点。
c++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int rangeSumBST(TreeNode* root, int low, int high) {
int sum=0;
queue<TreeNode*> q({root});
while(!q.empty())
{
auto node=q.front();
q.pop();
if(node==nullptr) continue;
if(node->val>high) q.push(node->left);
else if(node->val<low) q.push(node->right);
else
{
sum+=node->val;
q.push(node->left);
q.push(node->right);
}
}
return sum;
}
};
python
# 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 = right
class Solution:
def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
total=0
q=collections.deque([root])
while q:
node=q.popleft()
if not node: #node 为空
continue
if node.val>high:
q.append(node.left)
elif node.val<low:
q.append(node.right)
else:
total+=node.val
q.append(node.left)
q.append(node.right)
return total
方法三 中序遍历 （递归和迭代的区别？）
c++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int total=0;
int low,high;
int rangeSumBST(TreeNode* root, int _low, int _high) {
low=_low,high=_high;
dfs(root);
return total;
}
void dfs (TreeNode *root)
{
if (root==nullptr) return ;
dfs(root->left);
if(low<= root->val && root->val <=high){ //注意写成low<= root->val <=high 不行
total+=root->val;
}
dfs(root->right);
}
};python
# 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 = right
class Solution:
def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
self.total=0
def dfs(node):
if node.left:
dfs(node.left)
if node.val > high:
return
if node.val>=low:
self.total+=node.val
if node.right:
dfs(node.right)
dfs(root)
return (self.total)