[알고리즘] 이진 탐색 트리(BST)합의 범위

이진 탐색 트리(BST)합의 범위

책 풀이

class Solution:
    def rangeSumBST(self, root: 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)

이진 탐색 트리는 왼쪽이 항상 작고, 오른쪽이 항상 크다는 것을 이용한다. 현재 노드 root가 L보다 작은 경우, 더 이상 왼쪽은 탐색할 필요가 없다.

class Solution:
    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
        stack, sum = [root], 0
        # 큐 연산을 이용해 반복 구조 BFS로 필요한 노드 탐색
        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