[leetcode 2024/02/17] 938. Range Sum of BST

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

LeetCode - The World's Leading Online Programming Learning Platform

 

1. 접근 방법

[low, high] 사이에 있는 값들의 sum을 반환하는 문제이다.

 

node.val > low 라면, 왼쪽으로 이동시켜 주었으며

node.val < high 라면, 오른쪽으로 이동시켜 주었다.

 

이진 트리에서 low와 high 노드를 찾아가는 느낌으로 코드를 구상하였다.

찾아가는 과정에서 찾은 노드는 low와 high 사이에 값이 있는 노드인지 확인해주고, 사이에 있다면, total 이라는 set에 값을 넣어주었다.

 

2. 코드

# 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:
        total = set()
        def range_node(node):
            if node is None:
                return
            if node.val >= low and node.val <= high:
                total.add(node.val)
            if node.val > low:
                range_node(node.left)
            if node.val < high:
                range_node(node.right)
    
        
        range_node(root)
        print(total)

        return sum(total)