LeetCode 풀기 - 938. Range Sum of BST

938. Range Sum of BST

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

Range Sum of BST - LeetCode

문제)

솔루션1) - inorder traversal

이진 트리의 전위, 중위, 후위 순회 뭐든 사용해도 상관없습니다.

트리의 전체를 순회하면서 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)

솔루션2) - stack 사용

stack 자료구조를 사용합니다.

이진 트리 구조를 이용해서 탐색 범위를 줄여가기 때문에 솔루션1) 보다 더 빠르게 range sum을 구할 수 있습니다.

# 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:
        stack = [root]        
        range_sum = 0
        
        while stack:
            node = stack.pop()
            
            if node:
                if low < node.val:
                    stack.append(node.left)
                
                if node.val < high:
                    stack.append(node.right)
                
                if low <= node.val <= high:
                        range_sum += node.val
                        
        return range_sum