# 109. Convert Sorted List to Binary Search Tree

{% embed url="<https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/>" %}

把Q108改成了在`linked list`上操作，此时长度无法直接获得，就不能定位中点。

{% content-ref url="108.-convert-sorted-array-to-binary-search-tree" %}
[108.-convert-sorted-array-to-binary-search-tree](https://xuqiangwen1994.gitbook.io/practice/108.-convert-sorted-array-to-binary-search-tree)
{% endcontent-ref %}

1. 比较暴力的解法是把`linked list`转换成`array`，然后复制Q108的操作。
2. 还可以利用`BST`的性质，先遍历获得`linked list`的长度，然后`in-order`去生成`BST`。但其实这个方法跟前一个相比并无显著优势，同样有临时的额外空间使用，同样需要遍历一次链表。
3. 利用快慢双指针，可以在不获取长度的前提下获得链表的中点，但在时间复杂度上有比较大的牺牲，好处是完全没有使用额外空间。

{% tabs %}
{% tab title="convert to array" %}

```python
class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        nums = []
        while head:
            nums.append(head.val)
            head = head.next
            
        def helper(left, right):
            if left <= right: 
                mid = (left + right)//2  # 取左中点
                root = TreeNode(val = nums[mid])
                root.left = helper(left, mid-1)
                root.right = helper(mid+1, right)
                return root
        
        return helper(0, len(nums)-1)
```

{% endtab %}

{% tab title="bottom-up grow" %}

```python
class Solution:
    def __init__(self):
        self.valPointer = None
            
    def grow(self, left, right):
        if right >= left:
            mid = (left + right) // 2
            getLeft = self.grow(left, mid-1)
            root = TreeNode(self.valPointer.val)
            root.left = getLeft
            self.valPointer = self.valPointer.next
            root.right = self.grow(mid+1, right)
            return root
        
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        length = 0
        counter = head
        self.valPointer = head
        while counter:
            length += 1
            counter = counter.next
        return self.grow(0, length-1)
```

{% endtab %}

{% tab title="two pointer" %}

```python
class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        if not head: return None
        if not head.next: return TreeNode(head.val)
        
        root = TreeNode()
        slow, fast = head, head.next.next 
        while fast and fast.next: 
            slow = slow.next
            fast = fast.next.next
        node = slow.next # right half
        slow.next = None # break up the linked list
        
        root.val = node.val
        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(node.next)
        
        return root
        
```

{% endtab %}
{% endtabs %}
