leetcode#108 Convert Sorted Array to Binary Search Tree

1. 문제

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

2. 나의 풀이

2.1 divide and conquer

• 어쨌든 리스트를 왼쪽 노드와 오른쪽 노드로 나누는 문제임
• 얼마다 균형있게 나누는가가 포인트 인데, 이미 오름차순으로 정렬되어 있기 때문에 가장 가운데 값을 루트로 두면 될 것 같음
  

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        head = TreeNode();
        
        def divideConquer(node, nums):
            # print("nums", nums)
            if len(nums) >= 3:
                print("3333")
                mid = len(nums)//2
                node.val = nums[mid]
                node.left = divideConquer(TreeNode(), nums[:mid])
                node.right = divideConquer(TreeNode(), nums[mid+1:])
                return node
            if len(nums) == 2:
                node.val=nums.pop()
                node.left = TreeNode(nums.pop())
                return node
            if len(nums) == 1:
                node.val=nums.pop()
                return node
        
        divideConquer(head, nums)
        return head

3. 남의 풀이