递归+中序遍历

时间复杂度O(N)每个节点遍历一遍
空间复杂度O(logN) 用到了栈空间，因为是高度平衡二叉树，高度logN

对二叉搜索树进行中序遍历最先遍历到的一定是最小的节点，对应链表头的值
链表有序的，因此会依次遍历到链表每个节点，所以只要知道链表长度就知道了二叉搜索树的节点数

按中序遍历方法，对左边一部分建立左子树，建立当前节点，再对右边一部分建立右子树

/**
 * 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:
    ListNode* p;
    TreeNode* sortedListToBST(ListNode* head) {
        p = head;
        int n = 0;
        while(p){
            n++;
            p = p->next;
        }
        //最后p==null了退出的循环，n对应的是null，所以链表有效节点是0~n-1对应的这些节点。
        p = head;
        return bst(0, n - 1);
    }
    TreeNode* bst(int start, int end){
        if(end < start) return NULL;
        int mid = (start + end)/2;
        TreeNode* leftpart = bst(start, mid - 1);
        TreeNode* node = new TreeNode(p->val);
        node->left = leftpart;
        p = p->next;
        TreeNode* rightpart = bst(mid + 1, end);
        node->right = rightpart;
        return node;
    }
};

递归 + 快慢指针

时间复杂度O(nlogn)
空间复杂度O(logn)
递归用到的栈空间。

用快慢指针找到中间节点，中间节点建立当前根节点，然后将链断成两个部分，递归得到左右子树

注意base case不仅要考虑到head为null的情况，还要考虑到mid==head的情况，即只有一个节点的情况
因为之后处理左子树还会将head作为输入，如果mid==head的话，将会无限递归下去，出现错误。

如果用数组将链表值都存储然后进行建立二叉树，就是用空间换时间，时间O(n)，空间O(n)

/**
 * 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:
    ListNode* p;
    TreeNode* sortedListToBST(ListNode* head) {
        if(!head) return NULL;
        //用快慢指针找到中间节点
        ListNode* mid = getmid(head);
        //建立当前树节点
        TreeNode* node = new TreeNode(mid->val);
        //BASE CASE 如果只有一个节点，如果不返回的话那么进行左侧建立时再输入head，会无限循环
        if(mid == head) return node;
        //递归进行左右子树建立
        node->left = sortedListToBST(head);
        node->right = sortedListToBST(mid->next);
        return node;
    }
    ListNode* getmid(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        ListNode* preslow = NULL;
        while(fast && fast->next){
            preslow = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        //将链从slow断开
        if(preslow) preslow->next = NULL;
        return slow;
    }
};