문제

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

문제 접근 및 풀이

height-balanced binary search tree에 대해서 처음 들어봐서 조금 생소했다.
처음 문제 읽고 든 생각은 어쨌든 가운데를 선택해서 양 옆으로 똑같은 행위를 해주면 되었다.
재귀 함수를 써야지! 하고 생각하며 접근하니까 탈출 조건을 먼저 생각해주어야 했다.
넘어온 노드가 없으면 null이고, 하나면 그냥 붙여주자는 생각을 했다.
생각한 알고리즘(간단한 슈도코드)대로 풀으니까 딱 하고 풀렸는데 쾌감 ㅜ_ㅠ😇 이맛에 알고리즘 푼다.

간단한 슈도 코드(?)

// 어쨌든 중앙 값 선택하자
	//중앙이 없어? 0개 이거나 1개 이거나 -> 처리해주자
// Math.floor를 써서 중앙 값을 찾자 (2개면 자동으로 맨 끝 값 선택)
// 왼쪽과 오른쪽의 재귀 처리
// return 현재 root 노드

결과

function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val;
  this.left = left === undefined ? null : left;
  this.right = right === undefined ? null : right;
}

var sortedArrayToBST = function (nums) {
  if (nums.length === 0) return null;
  if (nums.length === 1) return new TreeNode(nums[0]);

  const middleIndex = Math.floor(nums.length / 2);
  const root = new TreeNode(nums[middleIndex]);
  root.left = sortedArrayToBST(nums.slice(0, middleIndex));
  root.right = sortedArrayToBST(nums.slice(middleIndex + 1, nums.length));

  return root;
};

사담

DFS라는 것을 알고 풀어서 그런지 재귀라는 것이 요즘 잘(?) 떠오르는 중
(무엇을 가져올 것인가, 어떨때 탈출할 것인가...)
열심히 DFS와 BFS를 연습하는중! 이번주는 내내 Easy만 풀어야지
쉬운 문제를 골라서 푸니까 좀 기초가 잡히는 중이다. 트리와 그리드에 넘넘 약하군

this 때문에 화살표함수는 constructor가 없음
this에 대해 또 까먹어 버렸으니 정리해둬야 할 것 같음