[LeetCode#108] Convert Sorted Array to Binary Search Tree

❒ Description

---

날짜	2024.09.25 (수)
레벨	Easy
제목	Convert Sorted Array to Binary Search Tree
링크	https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/
자료구조	그래프 - BST
시간 복잡도	O(n)

이번 문제는 BST의 특징을 정확하게 파악하고 있어야 한다.

 

 

 

 

 

❒ Solution

---

public TreeNode sortedArrayToBST(int[] nums) {
    return construct(nums, 0, nums.length - 1);
}

public TreeNode construct(int[] nums, int lo, int hi) {
    if (lo > hi) return null;
    int mid = lo + (hi - lo) / 2;
    TreeNode node = new TreeNode(nums[mid]);
    node.left = construct(nums, lo, mid - 1);
    node.right = construct(nums, mid + 1, hi);
    return node;
}

배열의 중앙 값을 구하고, 그 중앙 값을 기준으로 좌,우의 배열을 재귀로 순환하면서 해결하는 방법이다.

`int mid = lo + (hi - lo) / 2`에서 lo를 더해주는 이유는 쪼개진 배열의 가장 앞 index를 기준으로 하기 위해서다.

 

 

 

 

 

---