BST: Convert Sorted List to Balanced BST

👩‍💻 문제

Objective:

The task is to develop a method that takes a sorted list of integers as input and constructs a height-balanced BST.

This involves creating a BST where the depth of the two subtrees of any node does not differ by more than one.

Achieving a height-balanced tree is crucial for optimizing the efficiency of tree operations, ensuring that the BST remains efficient for search, insertion, and deletion across all levels of the tree.

 

말 그대로, 리스트로 된 애를 트리로 만들어서 그 루트를 반환하는 문제! 

 

인풋은 [nums list], left index, right index 이다

 

 

💡 풀이

   def sorted_list_to_bst(self, nums):
        self.root = self.__sorted_list_to_bst(nums, 0, len(nums) - 1)

    def __sorted_list_to_bst(self, nums, left, right):
        if left > right:
            return None
        mid = (left+right)//2
        current = Node(nums[mid])
        
        current.left = self.__sorted_list_to_bst(nums, left, mid-1)
        current.right = self.__sorted_list_to_bst(nums, mid+1, right)
        return current

 

 

✍️ 해설

우선 리스트 길이가 0일 경우는, 아무 트리도 생성하지 않으므로 None 반환

그 외의 경우, 

중간 노드가 루트가 될테니 그걸 mid로 설정해주고 (left+right)//2 

현재 노드를 그 중간노드 값으로 만들어준다. 노드 생성 !

 

그 다음, 그 노드를 기준으로 left, right를 생성해주면 된다

left는 mid를 포함하지 않으면서 left ~ mid-1 까지의 값이 될거고

right는 mid를 포함하지 않으면서 mid+1 ~ right 까지의 값이 될거다

그렇게 재귀함수를 작성해주면 끝!

 

 

🥳 배운점

재귀함수가 은근히 문제를 쉽게 만들어주는 경향이 있다.