题目描述 有序链表转换二叉搜索树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

解题思路

拿到题目想的是先把链表中的值存在一个vector中，然后递归创建二叉搜索树。菜鸡什么时候才能成长啊，心累ing。
做完后借鉴大佬们的想法，用快慢指针来找到链表的中间节点，然后递归调用原函数。

代码

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if(!head) return nullptr;
        vector<int> nums;
        while(head){
            nums.push_back(head->val);
            head = head->next;
        }
        TreeNode *root = new TreeNode(nums[nums.size()/2]);
        root->left = sortedListToBST(nums, 0, nums.size()/2-1);
        root->right = sortedListToBST(nums, nums.size()/2+1, nums.size()-1);
        return root;
    }

    TreeNode* sortedListToBST(vector<int> nums, int i, int j) {
        if(i>j) return nullptr;
        int x = (i+j)/2;
        TreeNode *root = new TreeNode(nums[x]);
        root->left = sortedListToBST(nums, i, x-1);
        root->right = sortedListToBST(nums, x+1, j);
        return root;
    }

};

大佬们的代码，宝宝什么时候才能学会呀。

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