109. Convert Sorted List to Binary Search Tree

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def len(self, head):
        sz = 0
        i = head
        while i:
            sz += 1
            i = i.next

        return sz

    def buildTree(self, k):

        if k == 0:
            return None
        print(k)
        root = TreeNode(0)
        root.left = self.buildTree(k - (k//2) - 1)
        root.right = self.buildTree(k//2)
        return root

    def inorder(self, root, head):
        node = root
        st = []
        while st or node:
            if node:
                st.append(node)
                node = node.left
            else:
                node = st.pop()
                node.val = head.val
                head = head.next
                node = node.right

    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        root = self.buildTree(self.len(head))
        self.inorder(root, head)
        return root