LeetCode 108(Convert Sorted Array to Binary Search Tree, Python)

1. 문제 링크

• Convert Sorted Array to Binary Search Tree - LeetCode

Convert Sorted Array to Binary Search Tree - LeetCode

2. 문제 설명

• 오름차순으로 정렬된 리스트가 입력되었을 때 height-balanced 이진 트리 구조로 만들어 반환하기
  • height-balanced란? : 임의의 노드의 좌우 서브트리 깊이 차이가 1보다 크지 않아야 함.
• 예시) nums = [-10,-3,0,5,9]가 주어졌을 때 아래 트리 구조를 반환
•         0
         / \
       -3   9
       /   /
  -10  5
  

3. 처음 풀이(못 풀었음, 작동되지 않음)

• 아이디어는 앞에서부터 하나씩 꺼내어 노드, 왼쪽, 오른쪽에 넣는걸 반복하려 하였음. 
• 하지만 내려갈 수록 가지가 많아져서 반복 작업을 어떻게 구현해야할 지 답답하였음.

# 시도했던 흔적, 작동되지 않음.

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:

        temp = result = TreeNode(nums[0])
        # del nums[0]
        print(nums)
        
        temp = TreeNode(nums[0],TreeNode(nums[1]),TreeNode(nums[2]))
        print(temp)


        
        # def BST(nums,temp):
        #     if len(nums) > 0:
        #         temp = result = TreeNode(nums[0])
        #     if len(nums) == 1:
        #         temp = TreeNode(nums[0])
        #         del nums[0]
        #     elif len(nums) == 2:
        #         temp = TreeNode(nums[0],TreeNode(nums[1]),None)
        #         del nums[0:2]
        #     elif len(nums) > 2:
        #         temp = TreeNode(nums[0],TreeNode(nums[1]),TreeNode(nums[2]))
        #         del nums[0:3]
        #         print(nums,result,temp)
        #         BST(nums,temp.left)
        #         BST(nums,temp.right)
            
        #     return temp
            
        # BST(nums,temp)
        return result

4. 다른 풀이

• 힌트만 얻으려고 내 코드를 GPT에게 살짝 보여주었는데 정답을 알려줌.
• 주어진 리스트의 중간 지점을 잡아 루트 노드에 넣고, 왼쪽 절반 리스트는 왼쪽 서브 트리에, 오른쪽 절반 리스트는 오른쪽 서브 트리에 재귀 함수 처리

# 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
        mid = int(len(nums)/2)
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])
        return root

5. 배운 점

• 역시 이진 트리 구조에서는 재귀 함수가 자주 사용된다. 
• 이진 트리가 주어지고 판단하거나 순회하는 문제는 풀어보았는데 반대로 트리를 구성하는 것은 처음이라 어려웠다.