99클럽 코테 스터디 10일차 TIL + 이진 탐색 트리 (Binary Search Tree), BFS, [leetcode] Range Sum of BST

✨ 문제 

Range Sum of BST

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

 

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

 

 

 

✨ 개념

이진 탐색 트리 Binary Search Tree

- 이진 트리의 특수한 형태로 정렬된 구조를 갖고 있음.

- 왼쪽 서브트리에 있는 모든 노드의 값은 해당 노드의 값보다 작으며, 마찬가지로 오른쪽 서브트리에 있는 모든 노드의 값은 해당 노드의 값보다 크다.

- 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리여야함.

- 효율적인 탐색, 삽입, 삭제가 가능하고, 시간복잡도는 트리의 높이에 비례하며 일반적으로 O(log n)임.

- 삽입, 삭제 연산은 기존 트리 구조를 유지하며 수행. 삽입 시에는 특정 위치를 찾아 새로운 노드를 추가하고, 삭제 시에는 해당 노드 삭제 후 대체 노드를 배치함.

 

DFS

- 스택 또는 재귀를 사용해 구현 가능

- 한 정점에서 최대한 깊게 탐색 후 더이상 방문 가능한 정점이 없으면 이전 정점으로 돌아와 다시 탐색하는 과정을 반복함.

 

 

 

✨ 최종코드

 

/**
 * 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 {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null)
            return 0;
            
        int sum = 0;

        if (root.val >= low && root.val <= high)
            sum += root.val;
        if (root.val > low)
            sum += rangeSumBST(root.left, low, high);
        if (root.val < high)
            sum += rangeSumBST(root.right, low, high);

        return sum;
    }
}

 

root가 null인 경우 0을 리턴하고, 총합을 더할 변수 sum을 선언했다. 현재 노드의 값이 low와 high 사이이면 sum에 현재 노드 값을 더해준다. 이진 탐색 트리의 특성을 이용해 현재 노드 값이 low보다 크면 왼쪽 자식 노드를 재귀호출한다. 이유는 왼쪽 노드들에는 현재 노드값보다 작은 값들이 존재하므로 low와 현재 노드값 사이의 값들이 있을 수 있기 때문이다. 마찬가지로 현재 노드값이 high보다 작은 경우 오른쪽 자식 노드를 재귀호출한다. 오른쪽 노드들은 현재 노드값보다 큰 값들이 존재하므로 현재 노드값보다 크면서 high보다 작은 수들이 존재할 수 있기 때문이다.

탐색이 끝나면 low와 high사이에 존재하는 값들의 총합을 저장한 sum을 반환한다.

 

이 코드를 이해하면서 조건을 root.val < low일때 root.right를 탐색하고, root.val > high일 때, root.left를 탐색하도록 하면 안되는건가 했는데 실제로 해보니 안됐다. ㅋㅋ 저렇게 하면 안되는 이유는 지금 문제에서 찾아야하는 값은 low ~ high 사이의 값들인데 저건 찾는값의 반대되는 조건이기 때문에 경계값이 누락되는 문제가 발생한다. 찾는값의 범위에 해당하는 노드는 sum에 더해지기만 하고 자식 노드를 더이상 탐색하지 않기 때문에 값이 누락되는 것이다.

 

이 문제는 정말 이해하기 힘들었다. 정답 코드를 봐도 너무 헷갈리고 어떻게 풀어야하는지 이 문제야말로 감을 잡을 수가 없었다. 지금도 다 이해는 못했고 80% 정도만 이해한 것 같다. 그래서 설명도 쓰면서도 너무 헷갈려서 주절주절 다 써놨는데 ㅋㅋ 어쨋든 꾸준히 풀다보면 완벽히 이해하게 되겠지