Convert Sorted List to Binary Search Tree(Linked List,Divide and Conquer,Tree,Binary Search Tree,Binary Tree)

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

Given the head of a singly linked list where elements are sorted in ascending order, convert it to a 

height-balanced

 binary search tree.

 

Example 1:

Input: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.

Example 2:

Input: head = []
Output: []

 

Constraints:

• The number of nodes in head is in the range [0, 2 * 104].
• -105 <= Node.val <= 105

거두 절미하고 문제를 풀어보자

 

간단해 보이는데 어렵다.. GG

1. Python

풀이를 봐도 헛갈린다. Recursive를 이용한 풀이

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# 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 sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        def buildBST(nums:list, start:int,end:int):
            if start > end:
                return None
            mid = (start + end) // 2
            return TreeNode(nums[mid], buildBST(nums, start, mid - 1), buildBST(nums, mid + 1, end))

        nums = []
        while head:
            nums.append(head.val)
            head = head.next
        return buildBST(nums, 0, len(nums) - 1)

 

좀 더 직관적인 코드다

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# 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 sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        # edge case
        if not head :
            return None
        if not head.next:
            return TreeNode(head.val)
        
        slow = head
        fast = head
        prev = None

        # Middle Point 찾기 = slow
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next
        # Create the root node with middle point
        root = TreeNode(slow.val)

        # Disconnect the left part of the list
        if prev:
            prev.next = None
        
        #Recursively build left / right sub-tree
        root.left = self.sortedListToBST(head) # left sub-tree
        root.right = self.sortedListToBST(slow.next) # right sub-tree
        
        return root

 

2. C

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* helper(int arr[],int left, int right){
    if(left > right) return NULL;
    int mid = (left+right)/2;
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = arr[mid];
    root->left = helper(arr,left,mid-1);
    root->right = helper(arr,mid+1,right);
    return root;
}

struct TreeNode* sortedListToBST(struct ListNode* head) {
    if(!head) return NULL;
    if(!head->next){
        struct TreeNode* temp = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        temp->val = head->val;
        temp->left = NULL; // C 에선 이런 초기화 필요
        temp->right = NULL;
        return temp;
    }
    int arr[100000];
    int idx = 0;
    while(head){
        arr[idx++] = head->val;
        head = head->next;
    }
    return helper(arr,0,idx-1);
}

 

Array를 만들어서 list 값을 다 넣고,

 

그 이후에 array를 돌면서 binary search 기법을 이용한다..