LeetCode 938. Range sum of binary search tree

Title address (938. The range of binary search tree and )

https://leetcode-cn.com/problems/range-sum-of-bst/

Title Description

 Given the root of the binary search tree  root, The return value is in the range  [low, high]  The sum of the values of all nodes between .

 

 Example  1：

 Input ：root = [10,5,15,3,7,null,18], low = 7, high = 15
 Output ：32


 Example  2：

 Input ：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
 Output ：23


 

 Tips ：

 The number of nodes in the tree is in the range  [1, 2 * 104]  Inside 
1 <= Node.val <= 105
1 <= low <= high <= 105
 all  Node.val  Different from each other 

Ideas

DFS Traverse

Code

• Language support ：Python3

Python3 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: TreeNode, low: int, high: int) -> int:
        self.res = 0# Set public variables 
        def dfs(node:TreeNode):
            if low <= node.val <= high:
                # print(node.val)
                self.res += node.val
            if node.left:
                dfs(node.left)
            if node.right:
                dfs(node.right)
        dfs(root)
        return self.res

Complexity analysis

Make n Is array length .

• Time complexity ：$O(n)$
• Spatial complexity ：$O(1)$