leetcode刷題，總結，記錄，備忘109

leetcode109

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.

Subscribe to see which companies asked this question

使用二分法，然後分别分為2個分支，進行遞歸操作，還是比較簡單的，但是貌似算法耗時有點多，40ms，，但是在leetcode送出通過的解決方案中排的比較靠後。。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode * result;
    
    void funciton(vector<int> vi, TreeNode * root)
    {
        if (root == NULL)
        {
            root = new TreeNode(0);
            result = root;
        }
        
        if (vi.size() == 1)
        {
            root->val = vi[0];
            root->left = NULL;
            root->right = NULL;
        }
        else if (vi.size() == 2)
        {
            root->val = vi[0];
            root->left = NULL;
            root->right = new TreeNode(vi[1]);
        }
        else
        {
            int mid = vi.size() / 2;
            root->val = vi[mid];
            root->left = new TreeNode(0);
            root->right = new TreeNode(0);
            vector<int> vl(vi.begin(), vi.begin() + mid);
            vector<int> vr(vi.begin() + mid + 1, vi.end());
            funciton(vl, root->left);
            funciton(vr, root->right);
        }
    }
    

    TreeNode* sortedListToBST(ListNode* head) {
        vector<int> vi;
        if (head == NULL)
        {
            return NULL;
        }
        
        while (head)
        {
            vi.push_back(head->val);
            head = head->next;
        }
        
        funciton(vi, NULL);
        
        return result;
    }
};
           

然後在讨論區看到一個解法，受到的啟發，還記得leetcode之前有個判斷1個連結清單是否是循環的題，使用快慢指針，這個方法就是使用快慢指針，找到中間的指針，然後也是1分為2，遞歸做二分法，比較巧妙的做法，感覺比我自己想 的解法更好，下面也把這個解決方法貼出來。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * 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;
        }
        
        ListNode * fast = head;
        ListNode * slow = head;
        ListNode * pre = NULL;
        
        while (fast && fast->next)
        {
            fast = fast->next->next;
            pre = slow;
            slow = slow->next;
        }
        
        if (pre)
        {
            pre->next = NULL;
        }
        else
        {
            head = NULL;
        }
        
        TreeNode * root = new TreeNode(slow->val);
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(slow->next);
        
        
        return root;
    }
};