재귀 알고리즘 연습을 위해 LeetCode에서 Recursion 문제를 찾아보았다!

내가 아무리 초심자이지만 이정도는 20분 안에 풀 수 있겠지라는 생각으로 Easy 난이도 중에서도 성공율이 무려 83%나 되는 Range Sum of BST 문제를 풀어보기로 하였지만

나의 예상은 빗나가고 대략 1시간 반을 끙끙거리게 되었다.

그래도 마침 트리탐색을 입문해보고 싶었던 차에 쉬운 트리탐색 문제를 접하게된 점은 좋았다.

문제는 간단하다.

주어진 비선형자료 Root의 자식들 중에서 Low와 High 사이의 자식들의 값을 모두 더한 값을 return 하라 (사이 값에 Low와 High도 포함)

Root는 아래 이미지와 같이 root.val이 있고 root.left에는 root.val 보다 작은 값이 root.right에는 root.val 보다 큰 값이 들어있다. (또는 null)

처음에는 다른곳에서 꼬리재귀로 문제를 푸는 것이 깔끔해보여 꼬리재귀로 풀어보기 위해

return (left 탐색) + (right 탐색)

과 같은 시도를 해보았지만

마지막 재귀호출에서 이전으로 값을 전달해주는 부분에서 막혀 일단은 약간 단순하게 문제를 풀어보기로 했다.

.

1.카운트 값

let count = 0

카운트할 변수를 세팅한다.

.

2. 해당되는 값 찾기

조건에 해당되는 값인지 여부를 판단하는 if 문을 써보자.

if ( root.val <= high && root.val >= low ) { 
	console.log('더하자! ', root.val)
	count += root.val 
	}

만약 root.val 값이 low와 high 사이라면 조건에 맞기 때문에 count에 root.val을 더해주자.

.

3. left, right 탐색

left와 right 자식들도 똑같이 탐색해서 해당되는 값이 있는지 찾아보자

    // left가 null이 아니라면 left 탐색
    if ( root.left != undefined ) { 
        console.log('왼쪽 탐색')
        count += rangeSumBST(root.left , low , high) 
        }
    
    // right도 똑같이 해줌
    if ( root.right != undefined ) { 
        console.log('오른쪽 탐색')
        count += rangeSumBST(root.right , low , high) 
        }
    

주석에도 씌여있듯이 left또는 right가 undefined가 아니라면 탐색을 시도한다.

왜냐하면 root.val이 undefined 일 때 low, high 사이 값인지 if 문을 돌리면 에러가 났었기 때문이다.

그리고 그렇지 않다고 하더라도 undefined인 값 때문에 불필요하게 함수를 호출하여 스택을 하나 떠 쌓아 메모리를 낭비하는 것도 방지할 수 있다.

실행

이리하여 최종적인 코드형태는 다음과 같다.

function rangeSumBST(root: TreeNode | null, low: number, high: number ): number {
    console.log('현재값 ',root.val)

    let count = 0
    
    // low, high 사이의 값이라면 count에 root.val을 더함
    if ( root.val <= high && root.val >= low ) { 
        console.log('더하자! ', root.val)
        count += root.val }
    
    // left가 null이 아니라면 left 탐색
    if ( root.left != undefined ) { 
        console.log('왼쪽 탐색')
        count += rangeSumBST(root.left , low , high) }
    
    // right도 똑같이 해줌
    if ( root.right != undefined ) { 
        console.log('오른쪽 탐색')
        count += rangeSumBST(root.right , low , high) }
    
    
    return count
};

첫번째 조건인

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

에서 위 코드를 돌려보면 console에는 다음과 같이 찍힌다.

현재값  10
더하자!  10
왼쪽 탐색
현재값  5
왼쪽 탐색
현재값  3
오른쪽 탐색
현재값  7
더하자!  7
오른쪽 탐색
현재값  15
더하자!  15
오른쪽 탐색
현재값  18

우선 해당되는 최초 root.val인 10을 카운트에 더한뒤 왼쪽부터 탐색하고 오른쪽을 탐색하는 것을 볼 수 있다.

최초 시도 때는 한참 10만 return 하여 왜그런가 봤더니

왼쪽, 오른쪽을 탐색할 때 count +=를 빼먹어서
count를 return만 하고 더하지를 않아 count가 늘지 않고 있었다.

아직 재귀를 쓰면서 결과값을 이전 재귀로 넘겨주는 부분이 명확하게 머리에 그려지지 않는다.

코드를 다시 읽어보고 다음에 재귀 문제도 몇개 더 풀어보기로하자.