[LEET CODE] 938. Range Sum of BST

# Problem

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].   Constraints: The number of nodes in the tree is in the range [1, 2 * 104]. 1 <= Node.val <= 105 1 <= low <= high <= 105 All Node.val are unique.

주어진 범위 내에 있는 노드의 값 더하기

 

# My Answer

class Solution:
    val=0
    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
        if root.val==low or root.val==high:
            self.val+=root.val
            
        if root.val <= low and root.right:
            self.rangeSumBST(root.right,low,high)
        elif root.val >= high and root.left:
            self.rangeSumBST(root.left,low,high)
            
        elif root.val > low and root.val < high:
            self.val+=root.val
            if root.right:
                self.rangeSumBST(root.right,low,high)
            if root.left:
                self.rangeSumBST(root.left,low,high)
            
        return self.val

 

# Solution 1 - 재귀 구조 DFS로  브루트 포스 탐색

class Solution:
    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
        if not root:
            return 0

        return (root.val if L <= root.val <= R else 0) + \
               self.rangeSumBST(root.left, L, R) + \
               self.rangeSumBST(root.right, L, R)

DFS로 전체를 탐색하면서 주어진 범위 내에 있을 때만 값 더하고 아닐 경우 0을 더한다

 

# Solution 2 - DFS 가지치기로 필요한 노드 탐색

class Solution:
    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
        def dfs(node: TreeNode):
            if not node:
                return 0

            if node.val < L:
                return dfs(node.right)
            elif node.val > R:
                return dfs(node.left)
            return node.val + dfs(node.left) + dfs(node.right)

        return dfs(root)

주어진 범위에 들어가지 않는 노드들 제외 ( Brunch Pruning )

불필요한 탐색 최소화

 

# Solution 3 - 반복 구조 DFS로 필요한 노드 탐색

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

주어진 범위 내의 노드들을 stack에 쌓아 반복

 

# Solution 4 - 반복 구조 BFS로 필요한 노드 탐색

class Solution:
    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
        stack, sum = [root], 0
        # 큐 연산을 이용해 반복 구조 BFS로 필요한 노드 탐색
        위에 설명과 마찬가지
        while stack:
            node = stack.pop(0)
            if node:
                if node.val > L:
                    stack.append(node.left)
                if node.val < R:
                    stack.append(node.right)
                if L <= node.val <= R:
                    sum += node.val
        return sum

solution 3의 스택을 큐 형태로 바꾸어 bfs 구현

pop(0) -> 입력값이 매우 크다면 O(n)으로 성능 차이 남

pop() -> O(1)