Range Sum of BST

문제

이진탐색트리와 2가지 정수형을 주고 그 사이의 값들을 포함해 더하라는 문제다.

풀이

이진탐색트리가 어떻게 만들어지는지에 대해 먼저 생각을 했다.
주어진 root = [10,5,15,3,7,null,18], low=7, high = 15 을 가지고 차근히 만들어 본다.

1. 트리가 비어 있으므로 10을 루트 노드로 설정
2. 5는 루트 노드 10보다 작으므로 왼쪽 자식 노드로 삽입
3. 15는 루트 노드 10보다 크므로 오른쪽 자식 노드로 삽입
4. 3은 루트 노드 10보다 작고, 5보다도 작으므로 5의 왼쪽 자식 노드로 삽입
5. 7은 루트 노드 10보다 작고, 5보다는 크므로 5의 오른쪽 자식 노드로 삽입
6. null은 return
7. 18은 루트 노드 10보다 크고, 15보다도 크므로 15의 오른쪽 자식 노드로 삽입

이 과정을 통해 예시의 그림과 같은

트리를 만들 수 있다.

그렇다면 low값을 찾기 위해선 (4)의 과정을 거쳐야 하고 high값을 찾기 위해선 (3)의 과정을 거쳐야 한다. 그에 따른 코드를 짜보았다.

var rangeSumBST = function(root, low, high) {
    if (root === null) {
        return 0;
    }
    
    let result = 0;
    
    // 왼쪽 서브트리 탐색
    if (root.val > low) {
        result += rangeSumBST(root.left, low, high);
    }
    
    // 오른쪽 서브트리 탐색
    if (root.val < high) {
        result += rangeSumBST(root.right, low, high);
    }
    
    // 현재 노드의 값이 범위 내에 있으면 더함
    if (root.val >= low && root.val <= high) {
        result += root.val;
    }

    return result;
};

정말 오랜만에 만난 이진탐색트리라서 가물가물했으나 무사히 떠올려서 풀 수 있었다.