Convert Sorted Array to Binary Search Tree
์ด๋ถํ์์ ํ๋ฏ์ด ํธ๋ฆฌ๋ฅผ ๋ง๋ ๋ค.
์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋์ด ์๊ธฐ ๋๋ฌธ์ ์ค์์ ์๋ ๊ฐ์ root๋ก ํ๊ณ ,
์ฌ๊ท๋ฅผ ์ด์ฉํ์ฌ
์ฒ์~์ค์-1 ๊น์ง์ ๋ฆฌ์คํธ๋ก ์ผ์ชฝ ์๋ธ ํธ๋ฆฌ๋ฅผ,
์ค์+1 ~ ๋ ๊น์ง์ ๋ฆฌ์คํธ๋ก ์ค๋ฅธ์ชฝ ์๋ธ ํธ๋ฆฌ๋ฅผ
๋ง๋ ๋ค.๋ฆฌ์คํธ์ ๊ธธ์ด๊ฐ 1์ผ ๋๋ ๊ฐ์ด ๋ฆฌ์คํธ[0]์ธ ๋ ธ๋๋ฅผ,
0์ผ ๋๋ None์ ๋ฆฌํดํ์ฌ ์ฌ๊ท ์ข ๋ฃ ์กฐ๊ฑด์ ์ค์ ํด์ค๋ค.
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]: if len(nums) == 0: return None if len(nums) == 1: return TreeNode(nums[0]) mid = len(nums) // 2 root = TreeNode(nums[mid]) leftSub = nums[0:mid] rightSub = nums[mid+1:] root.left = self.sortedArrayToBST(leftSub) root.right = self.sortedArrayToBST(rightSub) return root