###### tags: `Leetcode` `medium` `tree` `list` `divide and conquer` `python`

# 109. Convert Sorted List to Binary Search Tree

## [題目連結:] https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

## 題目:
Given the ```head``` of a singly linked list where elements are **sorted in ascending order**, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.


#### [圖片來源:] https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

## 解題想法:
* 給一linked list，將其轉換為height balanced BST
* 想法:
* 求list的中點視為root
* 左右子樹分別遞歸

## Python: Sol1
* 使用兩pointer
* slow=head
* fast=head
* slow每次走一步
* fast每次走兩步
* 當fast到尾，slow即為中間
* 額外設一pointer:pre，紀錄slow的前一個位置:
* 用以切段: slow=root
* 左樹: head~pre
* 右樹: slow.next~tail

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
    def insert(self,node):
        if self.next==None:
            self.next=ListNode(node)
        else:
            self.next.insert(node)
    def printList(self):
        head=self
        ans=[]
        while head:
            ans.append(head.val)
            head=head.next
        print(ans)
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)
        
        
class Solution(object):
    def sortedListToBST(self, head):
        if not head:
            return None
        if not head.next:
            return TreeNode(head.val)
        mid = self.findMid(head)
        root = TreeNode(mid.val)
        #左子 head~pev
        root.left = self.sortedListToBST(head)
        #右子 slow(mid).next~end
        root.right = self.sortedListToBST(mid.next)
        return root
        
    def findMid(self,head):
        slow=head
        fast=head
        #設pre原因為切段
        #head到pre為前半段
        #slow至尾為後半段
        #root.left呼叫 self.sortedListToBST(head)時候，就可以使用前半段而已 不用再整條找
        prev=None
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next
        prev.next = None
        return slow
    
    
head=ListNode(10)
head.insert(-3)
head.insert(0)
head.insert(5)
head.insert(9)
head.printList()

result = Solution()
ans = result.sortedListToBST(head)
ans.printTree()

## Python: Sol2
* 將linked list轉為array，再將其轉為tree

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
    def insert(self,node):
        if self.next==None:
            self.next=ListNode(node)
        else:
            self.next.insert(node)
    def printList(self):
        head=self
        ans=[]
        while head:
            ans.append(head.val)
            head=head.next
        print(ans)
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)
        
        
class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: Optional[TreeNode]
        """
        nums=self.getNum(head)
        return self.buildTree(nums)
        
    def getNum(self,head):
        tmp=head
        res=[]
        while tmp:
            res.append(tmp.val)
            tmp=tmp.next
        return res
    
    def buildTree(self,nums):
        if not nums:
            return None
        mid=len(nums)//2
        root=TreeNode(nums[mid])
        root.left=self.buildTree(nums[:mid])
        root.right=self.buildTree(nums[mid+1:])
        return root
    
head=ListNode(10)
head.insert(-3)
head.insert(0)
head.insert(5)
head.insert(9)
head.printList() #[10, -3, 0, 5, 9]

result = Solution()
ans = result.sortedListToBST(head)
ans.printTree() #[0, -3, 9, 10, 5]