[LeetCode 938] Range Sum of BST (Java)

🚀 문제 분석

• 목표: 이진 탐색 트리(BST)가 주어졌을 때, 값이 [low, high] 범위에 포함되는 모든 노드의 합을 구합니다.
• 핵심: BST는 Left < Root < Right의 정렬된 구조를 가집니다. 이 속성을 이용하면 특정 범위 밖의 서브트리는 탐색에서 아예 배제할 수 있습니다.

💡 해결 전략: 조건부 재귀 탐색 (Pruning)

전체 트리를 모두 뒤지는 대신, 현재 노드의 값(root.val)을 기준으로 탐색 범위를 좁힙니다.

1. 현재 값이 low보다 작은 경우: 왼쪽 서브트리는 볼 필요가 없습니다. 더 큰 값들이 있는 오른쪽만 확인합니다.
2. 현재 값이 high보다 큰 경우: 오른쪽 서브트리는 볼 필요가 없습니다. 더 작은 값들이 있는 왼쪽만 확인합니다.
3. 범위 내에 있는 경우: 현재 값을 결과에 더하고, 좌우 서브트리 모두 탐색을 이어갑니다.

💻 구현 코드 (Java)

public class Solution_Leetcode_938 {

    public int rangeSumBST(TreeNode root, int low, int high) {
        // 기저 사례: 노드가 없으면 0 반환
        if (root == null) {
            return 0;
        }

        // 1. 현재 노드 값이 low보다 작으면, 오른쪽만 탐색 (가지치기)
        if (root.val < low) {
            return rangeSumBST(root.right, low, high);
        }

        // 2. 현재 노드 값이 high보다 크면, 왼쪽만 탐색 (가지치기)
        if (root.val > high) {
            return rangeSumBST(root.left, low, high);
        }

        // 3. 범위 내에 있다면 현재 값 + 좌우 탐색 결과 합산
        return root.val
                + rangeSumBST(root.left, low, high)
                + rangeSumBST(root.right, low, high);
    }
}

🧐 기술적 고찰

• 재귀적 최적화: 단순히 모든 노드를 합산한 뒤 필터링하는 방식보다 훨씬 빠릅니다. 범위를 벗어나는 즉시 한쪽 방향의 탐색을 통째로 생략하기 때문입니다.
• BST 속성 활용: 이진 탐색 트리의 구조적 특징을 알고리즘의 성능 개선에 직접적으로 사용한 좋은 사례입니다.
• 공간 복잡도: 재귀 호출 스택의 깊이는 트리의 높이($H$)에 비례하므로 $O(H)$의 공간을 사용합니다.