greentea31's Note

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

풀이 과정

이진 탐색 트리에서 low <= node.val <= high인 노드의 합을 구하는 문제이다.

이진 탐색 트리의 특성상 어떤 노드의 왼쪽 서브 트리에는 더 작은 노드 값을 가지고 있는 노드들만, 오른쪽 서브 트리에는 더 큰 노드 값을 가지고 있는 노드들만 존재한다.

루트 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리 순으로 순회하는 전위 순회 방법으로 문제를 해결하였다.

현재 순회중인 노드 값이 low 보다 낮다면, 이진 탐색 트리의 특성상 왼쪽 서브 트리에 있는 노드들은 low보다 작은 값을 가질 것이므로, 순회할 필요가 없고, 현재 순회중인 노드 값이 high보다 크다면, 오른쪽 서브 트리에 있는 노드들은 high보다 큰 값을 가질 것이므로 마찬가지로 순회할 필요가 없다.

위와 같은 특성을 이용하면 풀이 시간이 줄어들지만, 그냥 모든 노드를 다 탐색해도 시간 초과가 발생하지는 않는 문제였다.

소스 코드

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