1. 오늘의 문제

Range Sum of BST

• 출처 : leetcode

2. 문제 분석

• 이진 탐색 트리의 루트 트리 : root

• low, high : 정수형 변수

• 리턴 값 : [low, high] range의 모든 노드가 갖고 있는 값의 합

• 트리의 범위 : 1부터 (2 * 10^4) 까지

• 노드가 갖고 있는 값 : 1 부터 10^5 까지

• 1 <= low <= high <= 10^5

• 입출력 예시

  • Input : root = [10, 5, 15, 3, 7, null, 18], low = 7, high = 15

  • Output : 32

  • Explanation : low부터 high 사이의 값들의 합 = 7 + 10 + 15 = 32
    
    

  • Input : root = [10, 5, 15, 3, 7, 13, 18, 1, null, 6], low = 6, high = 10

  • Output : 23

  • Explanation : low부터 high 사이의 값들의 합 = 6 + 7 + 10 = 23

3. 문제 풀이

1. 이진 탐색 트리는 root를 기준으로 왼쪽은 root보다 작은 수, 오른쪽은 root보다 큰 수이기 때문에 그 특성 활용
2. 재귀 함수를 통한 순회 : 노드를 다 쪼개면서 확인
3. 재귀를 위해 sum은 전역 변수로 선언
4. Base Case : 특정 node가 low와 high 사이라면 node의 값을 sum에 더함
5. 재귀 조건

• 특정 노드의 왼쪽 서브트리 순회
• 특정 노드의 오른쪽 서브트리 순회

4. 구현 코드

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int sum = 0;
    public int rangeSumBST(TreeNode root, int low, int high) {
        
        // 노드의 값이 null인 것은 제외하기 위해 0 return
        if (root == null) {
            return 0;
        }

        // Base Case : 특정 node의 값이 low와 high 사이에 있으면 sum에 더함
        if (root.val >= low && root.val <= high) {
            sum += root.val;
        }
        // 재귀 조건 : 특정 노드의 자식들도 Base Case 만족하는지 확인
        if (root.val > low) {
            rangeSumBST(root.left, low, high);
        }
        if (root.val < high) {
            rangeSumBST(root.right, low, high);
        }
        
        return sum;
    }
}

5. 오늘의 회고

• 역시 재귀 호출은 너무 힘들고 어려운 것 같습니다. 논리적으로 이해하기가 좀 빡센 느낌.. 연습하다보면.. 잘해지겠지..
• 권장 시간이 30분이었지만... 나는 43분.. 오늘을 발판 삼아 재귀 호출과 이진 탐색 트리에 대해 더 잘 알게 되었다!
  

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL