leetcode medium : Convert Sorted List to Binary Search Tree

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

Convert Sorted List to Binary Search Tree - LeetCode

 

* 풀기 전

푸는 방법은 여러 가지가 있을거같은데 AVL트리 ADT를 만들어서 인풋을 다 넣어줘도 되고 (근데 평소에 avl트리를 빨리 구현할 수 있을 정도로 많이 만들어본게 아니라면 비효율적이겠지?) 링크드리스트에서 값을 다 가져와서 리스트를 만들어놓고 median을 부모노드로 트리를 만드는 과정을 재귀적으로 수행해도 될거같다. 근데 후자의 방법은 메모리를 많이먹긴함. 상수조건 보니까 인풋은 최대 20000개. 메모리 문제는 없을거같긴한데 만약 면접관이 공간복잡도를 물어보고 줄여보라고 하면 어떡하지?ㅋㅋ.. 일단 정답 맞추고 생각해볼까

 

* 풀이

class Solution:
    def linked_list_to_pylist(self, head):
        lst = []
        while head:
            lst.append(head.val)
            head = head.next
        return lst
    
    def median_index(self, lst):
        return (len(lst) - 1) // 2
    
    def make_bst_from_lst(self, lst):
        if not lst:
            return None
        
        mi = self.median_index(lst)
        head = TreeNode(lst[mi])
        head.left = self.make_bst_from_lst(lst[:mi])
        head.right = self.make_bst_from_lst(lst[mi+1:])
        return head
    
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        inputlist = self.linked_list_to_pylist(head)
        answer = self.make_bst_from_lst(inputlist)
        return answer

 

 

 

* 다른 사람 풀이

def sortedListToBST(self, head: ListNode) -> TreeNode:        
        if not head:
            return         
        if not head.next:            
            return  TreeNode(head.val)        
        pre , slow , fast = None, head, head
        while fast and fast.next:                                
            pre = slow
            slow = slow.next
            fast = fast.next.next            
        pre.next = None                
        root = TreeNode(slow.val)
        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(slow.next)
        return root

미쳤네 그냥 ㅋㅋ.. slow는 한스텝씩, fast는 두스텝씩 순회해서 fast가 끝까지 가면 slow는 중위값을 가리키는 원리.

대신 left와 right로 recursion이 일어날때마다 계속 순회를 해야되니까 순회비용만 n log n이 될거같다.