99클럽 코테 스터디 10일차 TIL(5월 30일) + 알고리즘 DFS

[문제 링크]

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

 

[문제 사고]

문제의 주제가 DFS라는 부분을 알고는 있었지만 예시를 보고 정렬과 완전 탐색으로 접근하였지만 실패하고 정답을 보며 DFS로 코드를 구현하고 공부해 보았다.

 

[문제 해결]

1. DFS를 구현하기 위해 재귀 함수를 사용하여 코드를 설계한다.
2. 순차적으로 조건문을 작성해 나아가는데, 첫번째 조건으로 주어진 트리 노드가 없는 경우 0을 반환하도록 작성한다.
3. 조건에 맞는 값들을 더해 나아갈 임의의 변수 answer을 선언 후 0 값을 할당해준다.
4. 두번째 조건으로 주어진 범위 내에 트리 노드의 헤더 노드 값이 포함되면 헤더 노드를 answer 변수에 더해준다.
5. 세번째 조건부터 재귀함수가 구현되는데 트리 노드의 왼쪽 노드들에 해당하는 root.left의 값이 존재한다면 재귀 함수를 다시 호출하면서 전달되는 인자값 중 첫번째 인자 값을 왼쪽 노드를 반복적으로 탐색하도록 코드를 작성한다.
6. 마지막 조건은 왼쪽 노드를 탐색하는 것과 같은 방식으로 오른쪽 노드를 탐색하는 방식으로 코드를 작성해준다.
7. 재귀 함수를 호출해가며 조건에 맞는 값들을 answer 변수에 누산하여 결과값을 도출해낸다.

 

[작성 코드]

/**
 * 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) {
    if(!root) return 0;
    let answer = 0;
    if(low <= root.val && root.val <= high) answer += root.val;
    if(root.left) answer += rangeSumBST(root.left, low, high);
    if(root.right) answer += rangeSumBST(root.right, low, high);
    return answer;
};

 

[문제 회고]

DFS라는 알고리즘의 정말 기본적인 개념만 알고 있었지 활용하는 방법과 코드로 구현하는 방법은 몰랐다. 하지만 재귀 함수를 사용하여 구현해 나아간다는 점을 보고 이해는 완벽하게 하였다. 처음에는 root 자체가 트리 노드임에도 불구하고 배열로 표현이 되길래 오름차순 정렬 후 이진 탐색이나 완전 탐색을 통해 값을 구해야겠다고 생각했지만 실제로 배열의 형태가 아니였어서 멘붕이 왔었다. 그래서 트리 노드가 객체 형태임을 알아차리고 객체를 배열로 변환 후 다시 시도하였지만 역시나 실패를 하여서 정답을 참고하여 재귀 함수로 구현을 하게 되었다. DFS를 구현하는 방법에는 재귀 함수 말고도 스택을 사용하는 방법도 있고 문제에 따라서 완전 탐색이 필요없는 문제인 경우도 있다고 한다. 그러한 문제들도 풀어보고 공부를 해보아야겠다.