[OJ.leetcode] convert-sorted-list-to-binary-search-tree

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

/* Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. 

 

[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;

    }

};