链接
https://leetcode-cn.com/problems/range-sum-of-bst/
耗时
解题:21 min
题解:8 min
题意
给定二叉搜索树的根结点 root,返回值位于范围 [low, high] 之间的所有结点的值的和。
提示:
- 树中节点数目在范围 [1, 2 * 10^4] 内
- 1 <= Node.val <= 10^5
- 1 <= low <= high <= 10^5
- 所有 Node.val 互不相同
思路
因为是 BST,所以 dfs 遍历整棵树,如果当前节点值小于 low,直接到右子树去找,如果当前节点值大于 high,直接到左子树去找,剩下的情况就是符合范围的值,将当前节点值加入答案。
时间复杂度:
O
(
n
o
d
e
)
O(node)
O(node)
AC代码
class Solution {
public:
int rangeSumBST(TreeNode* root, int low, int high) {
if(root == NULL) return 0;
int now_val = 0, l_sum = 0, r_sum = 0;
if(root->val < low) {
r_sum = rangeSumBST(root->right, low, high);
}
else if(root->val > high) {
l_sum = rangeSumBST(root->left, low, high);
}
else {
now_val = root->val;
if(root->val > low) {
l_sum = rangeSumBST(root->left, low, high);
}
if(root->val < high) {
r_sum = rangeSumBST(root->right, low, high);
}
}
return now_val + l_sum + r_sum;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)