938. Range Sum of BST
给你一棵 binary search tree 还有目标 range = [low, high]
要你回传这棵树中 value 介于 [low, high] 间的所有 node 的总和
Example 1:
https://assets.leetcode.com/uploads/2020/11/05/bst1.jpg
Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.
Example 2:
https://assets.leetcode.com/uploads/2020/11/05/bst2.jpg
Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23
Explanation: Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23.
思路:
1.其实可以当成 binary tree 直接找所有 node 就好 左右子树都递回下去找
把那些 low <= value <= high 的 node 加起来就好 时间复杂度O(node数)
2.要用到 BST 的性质的话 就是把 value 和 low, high 拿去比较
value > high 的话: value 右子树全部都比 high 大，所以不用递回找右子树
value < low 的话: value 左子树全部都比 low 小，所以不用递回找左子树
时间复杂度不变就是了
Python code:
# 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: Optional[TreeNode], low: int, high: int) ->
int:
if not root:
return 0
res = 0
if root.val <= high:
res += self.rangeSumBST(root.right, low, high)
if root.val >= low:
res += self.rangeSumBST(root.left, low, high)
if low <= root.val <= high:
res += root.val
return res