convert-sorted-list-to-binary-search-tree

gistfile1.txt

/* Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. 
 
https://oj.leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
 
[1,2,3,4,5]
     3
    /  \
   2    5  
  /    /
 1    4
 
[1,2,3,4,5,6,7,8,9,10,11]
       6
      /  \
    4     10
   / \    /  \ 
  2   5  8    11
 / \    /  \ 
1   3  7   9
 
*/
/*성수님 해답 O(n): 
https://gist.github.com/seongsu/428dd11d56184fe163d2
*/
 
/*광성님 해답 O(nlogn):
class Solution {
public:
    TreeNode *sortedListToBST(ListNode *head) {
        if (head == NULL)
            return NULL;
        
        if (head->next == NULL) {
            TreeNode* node = new TreeNode(head->val);
            return node;
        }
        
        ListNode* mid_prev = head;
        ListNode* runner = head->next->next;
    
        while (runner != NULL && runner->next != NULL) {
            runner = runner->next->next;
            mid_prev = mid_prev->next;
        }
        
        ListNode* mid_node = mid_prev->next;
        mid_prev->next = NULL;
        
        
        TreeNode* root = new TreeNode(mid_node->val);
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(mid_node->next);
        
        return root;
    }
};
 */
 
/*
'balanced' 가 힌트이므로 middle 값을 찾아야한다는 접근은 초기에 쉽게 가능하다. 하지만 single linkedlist 이므로 매번 middle 찾을 때마다 O(n)을 순회해야하고, 함수 콜 깊이가 O(logn)이 되므로 총 시간 복잡도는 O(nlogn)이다. 
 
여기서 O(n)을 어떻게 찾느냐? 반드시 중간값부터 찾아야 한다는 고정관념을 버리고, 이미 '정렬'된 리스트라는 사실에서 힌트를 얻어서, 매번 두부분으로 쪼갠다음 양쪽을 inorder로 'bottom-up'방식으로 엮어 갈수도 있다는 사실을 발견하면 문제 해결. 구현도 꽤 까다롭다.
*/


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 
class Solution {
    public:
    TreeNode *sortedListToBST(ListNode *head) {
        if(head == NULL) return NULL;
        
        if(head->next == NULL) {
            return new TreeNode(head->val);
        }
        
        ListNode* runner = head;
        ListNode* midliner = head;
        ListNode* midPrev = head;
        
        while(runner != NULL && runner->next != NULL) { //test n = 2, 3
            runner = runner->next->next;
            midPrev = midliner;
            midliner = midliner->next;
        }
        
        TreeNode* root = new TreeNode(midliner->val);
        midPrev->next = NULL;
        
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(midliner->next);
        
        return root;
    }
};