[리트코드(LeetCode)] 938번 Range Sum of BST

문제

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

Range Sum of BST - LeetCode

이진 탐색 트리(BST)가 주어졌을 때 L 이상 R 이하의 값을 지닌 노드의 합을 구하는 문제다.

예시

Example 1:

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

 

Example 2:

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

풀이

# 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:
        def dfs(node):
            if not node:
                return 0
	# 현재 노드의 값이 low 보다 작으면, low 보다 작은 값들은 왼쪽 서브트리에 있을 것
            if node.val < low:
                return dfs(node.right)
	# 현재 노드의 값이 high 보다 크면, high 보다 큰 값들은 오른쪽 서브트리에 있을 것
            elif node.val > high:
                return dfs(node.left)
            return node.val + dfs(node.left) + dfs(node.right)

        return dfs(root)

 

- 이진 트리에서 dfs를 사용하여 노드를 방문하면서 주어진 범위 내의 값을 누적해서 반환한다.

- 이진 탐색 트리는 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들이 지닌 노드들이 있고, 오른쪽 서브트리에는 그 노드의 값과 같거나 큰 값들을 지닌 노드들로 이루어져 있다. 즉 현재 노드 root가 low보다 작을 경우, high 보다 클 경우 각각 왼쪽과 오른쪽을 탐색할 필요가 없다.

- 각 상황에 따라 불필요한 탐색을 줄이고, 필요한 경우에만 해당 방향으로 탐색을 진행하도록 한다.

 

참조 : 박상길, 파이썬 알고리즘 인터뷰  https://github.com/onlybooks/algorithm-interview