알고리즘, 자료구조에 대해 하나도 모르는 상태로 leetcode 문제를 만났다. 내 머리가 나쁘다는 사실을 매 초마다 느끼며 트리구조와 이진 탐색트리에 대해 알아보았다. 문제를 보면
이진 탐색 트리를 이용해 트리구조 안 범위에 해당하는 합 구하기
예) 위와 같은 트리구조에서 7 < value < 15 사이의 값들의 총합을 구하는 것
찾아보니 BST 란 Binary Search Tree, 이진 탐색 트리라는 의미였다.
이진 탐색 트리의 특징으로는
- 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가있는 노드 만 포함됩니다
- 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가있는 노드 만 포함됩니다.
- 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리 여야합니다.
- 중복된 키를 허용하지 않습니다.
쉽게 이해해보면 왼쪽부터 값의 크기대로 정렬된 트리모양 이라는 것
class Solution {
func rangeSumBST(_ root: TreeNode?, _ L: Int, _ R: Int) -> Int {
var sum = 0
guard let node = root else { return sum }
if L <= node.val && node.val <= R {
sum += node.val
}
if L < node.val {
sum = sum + rangeSumBST(node.left, L, R)
}
if node.val < R {
sum = sum + rangeSumBST(node.right, L, R)
}
return sum
}
}
풀이의 결과는 다음과 같다. 하지만 나는 답을 봐도 왜 이렇게 쓴건지 이해가 되질 않았다. 이런저런 것들을 참고하고 이해한 바로는
위에서 아래로 10부터 시작해 값이
1. 범위 안에 있는 경우 : sum에 값을 더한다. 그리고왼쪽, 오른쪽 모두 조건에 맞는 값이 존재 할 수 있으니양 쪽 노드 둘 다 점검한다.
2. 범위의 최소 값보다 작은 경우 :이 값보다 왼쪽에 있는 값들은 모두 범위에서 벗어나기 때문에 점검할 필요가 없다. 오른쪽으로만 탐색을 실시한다.
3. 범위의 최대 값보다 큰 경우 : 위와 같은 이유로 왼쪽으로만 탐색한다.
어떻게 보면 간단하지만 코드를 한줄씩 읽다보면 간단하지 않다. 
-
rangeSumBST(node.right, L, R) <- 이 함수에 걸릴 때마다 함수안에 함수를 또 들어가는
재귀의 개념이 포함됐기 때문이다. 인셉션도 아니고 머리 터진다 진짜. -
코드 구조도 진짜 인셉션이랑 비슷하기도 하다. 쭉 쭉 쭉 10 -> 5 -> 7 에 해당하는 node.val을 통해 함수 안으로 들어가서 최종 sum 값을 리턴할때는 꿈속에 꿈안에서 빠져나오듯이 다다다 return 0 return 7 return 17 이런식으로 값을 리턴한다.
