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

 

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

Range Sum of BST - LeetCode

 

 1. 재귀 구조 DFS로 브루트 포스 탐색

 

 DFS로 전체를 탐색한 다음, 노드의 값이 low와 high 사이일 때만 값을 부여하고, 아닐 경우에는 0을 취해 계속 더해 나가면 쉽게 구할 수 있다.

# 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:
    sum=0
    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)

 그러나 이 방식은 모든 노드를 탐색하는 브루트 포스 풀이이다. 좀 더 최적화를 해보자.

 

 2. DFS 가지치기로 필요한 노드 탐색

 DFS로 탐색 하되 low,high 조건에 해당되지 않는 가지를 쳐내는 형태로 탐색에서 배제하도록 다음과 같이 구현해보자.

class Solution:
    sum=0
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        
        def dfs(node):
            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:
    sum=0
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        
        if root:
            if root.val>=low and root.val<=high:
                self.sum+=root.val
                self.rangeSumBST(root.left,low,high)
                self.rangeSumBST(root.right,low,high)

            elif root.val <low:
                self.rangeSumBST(root.right,low,high)

            elif root.val >high:
                self.rangeSumBST(root.left,low,high)


        return self.sum

 이 경우 불필요한 탐색은 배제하게 되므로 탐색 효율이 매우 높다. 필요한 노드만 탐색하여 해당 노드의 값들을 더해 나가게 된다.