99클럽 코테 스터디 1일차 TIL 938. Range Sum of BST

leetcode.com 938. Range Sum of BST

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

 

 

 

 

 

이진 검색 트리의 범위 합 이진 검색 트리의 루트 노드와 두 정수 low와 high가 주어질 때, 값이 [low, high] 범위에 포함되는 모든 노드의 값의 합을 반환하세요.

 

 

풀이)

이진 트리 사용

트리 전체를 순회하면서 val이 low, high의 사이 값인 경우 저장해서 sum을 구함

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        res = []
        
        def traversal(node):
            if node is None:
                return
            
            if low <= node.val <= high:
                res.append(node.val)
            if low < node.val:
                traversal(node.left)
            if node.val < high:
                traversal(node.right)
            
        traversal(root)
            
        return sum(res)