[Leetcode] 938. Range Sum of BST (JS)

출처

938. Range Sum of BST

문제

나의 코드

이진 탐색 트리 등과 같은 실제 자료 구조를 처음 문제로 접하게 되었다. 사실 알고리즘과 자료구조를 제대로 공부하고 있지 않기 때문에 이진 탐색 트리 라는 개념도 정확히 공부한 적이 없었다. 그 와중에 만난 이 문제는 나를 끝없는 어둠에 가두어놓기에 충분했다.

var rangeSumBST = function(root, low, high) {
    root.filter(x => x >= low && x <= high ? x : null).reduce((x, y) => x + y)   
};

문제를 당연하게도 완전히 이해하지 못했기 때문에 위와 같은 코드를 작성했다. root라는 input 요소가 당연하게 배열 형태로 주어진다고 생각했고 이에 따라 매우 간단한 코드를 작성했다. 하지만 당연히 결과는 FAIL..

머리를 싸매고 공부해도 도저히 해결되지 않는다는 것을 깨닫고 유튜브, 구글 검색 등 총동원해서 이진 탐색 트리에 대해 공부하기 시작했다.

나동빈님의 강의와 rats'go님의 블로그 그리고 현재 갖고 있는 책인 누구나 자료 구조와 알고리즘을 참고해서 공부했다.

이진 탐색 트리란?

• 이진 탐색(binary search)과 연결 리스트(linked list)를 결합한 자료 구조
• 이진 탐색의 효율적인 탐색 능력 + 연결 리스트의 효율적인 자료 입력과 삭제 기능

탐색 방법?

• 노드의 값 확인
• 찾고 있는 값이면 럭키!
• 찾고 있는 값이 현재 노드보다 작다면 왼쪽 하위 트리 검색
• 찾고 있는 값이 현태 노드보다 크면 오른쪽 하위 트리 검색

또 알아야할 것?

• 이진 트리를 검색하는 알고리즘은 루트 노드부터 시작
• 이진 탐색과 달리 이진 트리는 탐색 이외에 삽입과 삭제가 가능
• 이진 트리 탐색의 시간 복잡도는 O(log n)
• 이유는 각 단계를 수행할 때마다 값이 들어있을 남은 공간 중 반을 제거하기 때문!
• 다만, 이는 최선의 시나리오인 포화 균형 이진 트리에서만 한정

그래서 진짜 너의 코드는?

이진 탐색 트리에 대한 개념도 전혀 몰랐기 때문에 다른 분의 코드를 먼저 보고 이해하기로 했다. 처음에는 코드를 보고도 전혀 이해가 가지 않았지만, 직접 root.val 값을 콘솔창에 출력해보고 다른 배열도 여러 번 넣어보니 조금은 알 것 같다는 느낌이 들었다.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} low
 * @param {number} high
 * @return {number}
 */
var rangeSumBST = function(root, low, high) {
    let sum = 0

    if (root === null) {
        return sum
    }
    console.log('현재값?', root.val)
    
    if (root.val > low) {
        console.log('현재값?', root.val)
        sum += rangeSumBST(root.left, low, high)
    }
    if (root.val >= low && root.val <= high) {
        console.log('더하자!', root.val)
        sum += root.val
    }
    if (root.val < high) {
        console.log('현재값?', root.val)
        sum += rangeSumBST(root.right, low, high)
    }
    
    return sum
};

현재값? 10
현재값? 10
현재값? 5
현재값? 5
현재값? 7
더하자! 7
현재값? 7
**더하자! 10**
현재값? 10
현재값? 15
현재값? 15
더하자! 15

위와 같이 실제로 코드의 실행 결과를 눈으로 보면서 하다보니 조금은 이해가 갈 수 있었다! 다만, 아직 이해가 가지 않는 부분은 저 더하자! 10 부분이 어떻게 if (root.val > low) 코드를 뛰어넘고 바로 다음으로 갈 수 있었냐는 것인데..

이전에 코드를 실행해서 컴퓨터가 값을 알고 있다는 가정일런지.. 이 부분은 공부하면서 더 알아봐야겠다!

실행 결과