E-938. Range Sum of BST

Loading...LeetCode

'''
通过条件限定, 进行中序遍历, 因此剪枝了.
Time: O(n)(注意与普通的在BST里面找点不一样, 这是一个范围, 所以是O(n).(普通的是O(H),
如果是平衡二叉树, 即Balanced Binary Search Tree, 就是O(logn)))
Space: O(H), 即树的高度, 因为range_sum最多被调用H次(因为进行了剪枝, 如果不剪枝, 就是n次)
'''
class Solution:
    def __init__(self):
        self.sum=0
    
    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
        def range_sum(root):
            if not root:
                return 0
            if L<=root.val:
                range_sum(root.left)
            if L<=root.val<=R:
                self.sum+=root.val
            if root.val<=R:
                range_sum(root.right)
            
        range_sum(root)
        return self.sum