見出し画像

ほぼ日刊競プロ leetcode 108. Convert Sorted Array to Binary Search Tree

108. Convert Sorted Array to Binary Search Tree

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.
A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

すでにソートされている数列がlist型で値が与えら得るのでそれを二分探索木にする.

考えたこと

いろいろ考えたけどできなかった...
参考にしたサイト↓
ゼロから始めるLeetCode Day100「108. Convert Sorted Array to Binary Search Tree」

よく考えたら二分探索と同じ考え方で行けそうだと考えた.

# 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 not nums:
           return None
       middle = len(nums)//2
       #print (middle)
       ans = TreeNode(nums[middle])
       ans.left = self.sortedArrayToBST(nums[:middle])
       ans.right = self.sortedArrayToBST(nums[middle+1:])
       #if nums[middle]
       return ans

この記事が気に入ったらサポートをしてみませんか?