[LeetCode] Convert Sorted Array to Binary Search Tree

🧑‍💻 언어 및 제출 결과

• 사용 언어: TypeScript
• 통과 여부: ✅

🧠 풀이 설명

오름차수로 nums가 주어지면 그에 맞춰서 이진 트리를 만들어야 되는 문제입니다
아주 친절하게도 sorting을 해주네요 중간 값이 root가 되어야 되니 Math.floor(nums.length / 2)를 해서 root로 지정해주고
left, right에 알맞는 값을 slice로 잘라서 재귀로 반복해주면 됩니다

function sortedArrayToBST(nums: number[]): TreeNode | null {
  if (nums.length === 0) return null;

  const midIndex = Math.floor(nums.length / 2);

  return new TreeNode(
    nums[midIndex],
    sortedArrayToBST(nums.slice(0, midIndex)),
    sortedArrayToBST(nums.slice(midIndex + 1))
  );
}

📊 시간/공간 복잡도

✅ 어떠한 근거로 시간/공간 복잡도가 이렇게 나왔는지 설명해주세요.

⚡️ 풀이의 속도와 메모리 등을 캡쳐해서 올려주세요.

• 시간 복잡도: O(n) - 요소를 한 번씩 처리하지만 slice 오버헤드 존재
• 공간 복잡도: O(n) - 결과 트리와 임시 배열

 

🙋‍♂️ 리뷰어에게

의도치 않게 제일 빠른 사람 코드랑 겹쳤는데 제건 3ms가 느리네요.. 왠지 모르겠는데 아시는 분 있다면 알려주세오