LeetCode/solutions/109. Convert Sorted List to Binary Search Tree.md

109. Convert Sorted List to Binary Search Tree

思路

根据一个有序链表建立一个平衡的搜索二叉树。

思路一

由于需要平衡的，所以每次都应该找到链表中间那个元素作为根节点，找到链表中间节点的方法就是快慢指针法，慢指针每次移动一步，快指针每次移动两步，这样当快指针 到达链尾时慢指针就处在中间位置。
每次查找需要O(n)的复杂度，次数为进行O(logn)量级，所以总的复杂度应该是O(nlogn)

思路二

为了更快地查找到中间元素，我们还可以考虑将链表元素用一个数组来存放，这样就可以用二分了。
每次查找复杂度变成了O(logn)，所以建树总的复杂度应该是O((logn)^2)，但是一开始建立数组时复杂度为O(n)，所以总的时间复杂度应该是O(n)级别（但实测此方法比思路一要慢）

C++

思路一

class Solution {
public:
    TreeNode *sortedListToBST(ListNode* head) {
        if (!head) return NULL;
        if (!head->next) return new TreeNode(head->val);
        ListNode *slow = head, *fast = head, *last = slow;
        while (fast->next && fast->next->next) {
            last = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        last->next = NULL;
        TreeNode *cur = new TreeNode(slow->val);
        if (head != slow) cur->left = sortedListToBST(head);
        cur->right = sortedListToBST(fast);
        return cur;
    }
};

思路二

class Solution {
private:
    TreeNode* helper(vector<int>& nodes, int low, int high){
        if(low > high) return NULL;
        int mid = (high - low) / 2 + low;
        TreeNode* root = new TreeNode(nodes[mid]);
        root -> left = helper(nodes, low, mid - 1);
        root -> right = helper(nodes, mid + 1, high);
        return root;
    }
public:
    TreeNode* sortedListToBST(ListNode* head) {
        vector<int>nodes;
        while(head){
            nodes.push_back(head->val);
            head = head -> next;
        }
        return helper(nodes, 0, nodes.size()-1); 
    }
};