题目地址：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 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发