ほぼ日刊競プロ leetcode　938. Range Sum of BST

938. Range Sum of BST

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

考えたこと

上記のように２分木になっているのでDFSでいけると考えた．しかも何も考えずにpreorderで行けると考えた．

# 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:
       self.ans = 0
       def help(root):
           if root:
               if  low <=root.val and root.val<=high:
                   self.ans+=root.val
               help(root.left)
               help(root.right)
           #print ("ans="+ str(self.ans))
           return self.ans
       return help(root)

しかしこの木構造の場合，ノードに左側についている物は，ノード自身のvalより必ず小さく，右に着いている物は必ず大きいので，探索範囲を狭めることで，高速化できると考えた．

# 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:
       self.ans = 0
       def help(root):
           if root:
               if  low <=root.val and root.val<=high:
                   self.ans+=root.val
               if low<root.val:
                   help(root.left)
               if root.val<high:
                   help(root.right)
           #print ("ans="+ str(self.ans))
           return self.ans
       return help(root)

上記のようにif文を使うことによって，ノードのvalueが最小値より大きい場合は最小値により近い小さい値がある可能性があり，最大値より小さい場合は最大値により近い大きな値がある可能性に絞り探索している．