LeetCode 230 - Kth Smallest Element in a BST (Medium)

문제

LeetCode - 230번

풀이 과정

이진 검색 트리 에서 k번째 원소를 찾는 문제입니다.

이진 검색 트리 는 루트 노드가 해당 노드의 왼쪽 자식 노드보다 크고 오른쪽 노드보다 작은 값을 가집니다.
따라서 이를 중위 순회 할 경우 키 값이 정렬된 순서대로 방문한다는 것을 알 수 있습니다.
이를 활용하여 중위 순회를 하는 함수를 만들고 k 번째 노드에 방문했을 때를 기록하여 답을 구하도록 하였습니다.

코드

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  const memo = new Array(nums.length).fill(-1);

  function dp(i) {
    if (i >= nums.length) return 0;
    if (i === nums.length - 1) return nums[i];

    if (memo[i] !== -1) return memo[i];

    memo[i] = Math.max(dp(i + 1), dp(i + 2) + nums[i]);
    return memo[i];
  }

  return dp(0);
};