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