# 0109. Convert Sorted List to Binary Search Tree
###### tags: `Leetcode` `Medium` `Linked List` `Binary Search Tree`
Link: https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
## 思路
### 思路一 $O(NlogN)$ $O(logN)$
思路不难
每次找到中间点，然后把linkedlist分开，最后再用recursion建成tree即可
debug很麻烦
- 快慢指针那里的while回圈里面的条件一定要写成```fast!=null && fast.next!=null```而不是```fast.next!=null && fast.next.next!=null```
- line 10 的base case一定要写，不然会进入无穷回圈
也就是当linkedlist里面只有一个值的时候就直接返回treenode，不需要再往下找了，不然line 11会死循环
### 思路二 $O(N)$ $O(logN)$
之所以思路一需要O(NlogN)就是因为每次recursive都需要一个一个遍历去找mid
这里用了inorder traversal的原理
inorder traversal是把一个binary search tree变成一个sorted list，反过来也同样可以，用recursive遍历，再把list里面的值一个个贴上去，同时还可以保证是一个balanced tree，因为可以用l和r控制左边tree的取值范围和右边tree的取值范围
## Code
### 思路一

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head==null) return null;
        ListNode fast = head, slow = head, temp = head;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            temp = slow;
            slow = slow.next;
        }
        if(slow==head) return new TreeNode(head.val);
        TreeNode treeHead = new TreeNode(slow.val);
        temp.next = null;
        treeHead.left = sortedListToBST(head);
        treeHead.right = sortedListToBST(slow.next);
        return treeHead;
    }
}

### 思路二

class Solution {
    ListNode head;
    
    public int findSize(ListNode head){
        ListNode curr = head;
        int len = 0;
        while(curr!=null){
            len++;
            curr = curr.next;
        }
        return len;
    }
    public TreeNode sortedListToBST(ListNode head) {
        int size = findSize(head);
        this.head = head;
        TreeNode root = inOrder(0, size); 
        return root;
    }
    public TreeNode inOrder(int l, int r){
        if(l >= r) return null;
        int mid = (l+r)/2;
        TreeNode left = inOrder(l, mid);
        TreeNode root = new TreeNode(head.val);
        head = head.next;
        root.left = left;
        root.right = inOrder(mid+1, r);
        return root;
    }
}