[코테] 리트코드 트리 938. Range Sum of BST

938. Range Sum of BST

문제 링크

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

문제 설명

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].

제한 사항

• The number of nodes in the tree is in the range [1, 2 * 10^4].
• 1 <= Node.val <= 10^5
• 1 <= low <= high <= 10^5
• All Node.val are unique.

입출력 예 #1

1. Input : root = [10,5,15,3,7,null,18], low = 7, high = 15
2. Output : 32
3. Explanation : Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.

입출력 예 #2

1. Input : root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
2. Output : 23
3. Explanation : Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23.

문제 풀이

1. 재귀 구조 DFS로 브루트 포스 탐색
2. DFS 가지치기로 필요한 노드 탐색
3. 반복 구조 DFS로 필요한 노드 탐색
4. 반복 구조 BFS로 필요한 노드 탐색

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        if not root:
            return 0
        
        return (root.val if low <= root.val <= high else 0) + \
                self.rangeSumBST(root.left, low, high) + \
                self.rangeSumBST(root.right, low, high)

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        def dfs(node: TreeNode):
            if not node:
                return 0
            
            if node.val < low :
                return dfs(node.right)
            elif node.val > high:
                return dfs(node.left)
            return node.val + dfs(node.left) + dfs(node.right)

        return dfs(root)

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        stack, sum = [root], 0 
        # 스택 이용 필요한 노드 DFS 반복
        while stack :
            node = stack.pop()
            if node:
                if node.val > low :
                    stack.append(node.left)
                if node.val < high :
                    stack.append(node.right)
                if low <= node.val <= high:
                    sum += node.val
        return sum

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        queue, sum = collections.deque([root]), 0 
        # 큐 연산을 이용해 반복 구조 BFS로 필요한 노드 탐색
        while queue :
            node = queue.popleft()
            if node:
                if node.val > low :
                    queue.append(node.left)
                if node.val < high :
                    queue.append(node.right)
                if low <= node.val <= high:
                    sum += node.val
        return sum