109. Convert Sorted List to Binary Search Tree

# 这道题跟108. Convert Sorted Array to Binary Search Tree很相近，不过这道题的data structure是linked list。
# 这道题的想法是先把linked list的长度算出来，然后根据linked list的长度构造出一个node的值为0的BST，
# 然后利用 inorder traversal 把linked list的值填到 BST 中替换原有的 0
class Solution:
    def linkedListSize(self, head):
        sz = 0
        tmp = head
        while tmp:
            sz += 1
            tmp = tmp.next

        return sz


    def buildTree(self, n):
        if n == 0 :
            return None

        mid = n // 2
        root = TreeNode(0)
        root.left = self.buildTree(n - mid - 1)
        root.right = self.buildTree(mid)

        return root

    def inorder(self, head, root):
        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
        """
        if not head:
            return None

        size = self.linkedListSize(head)
        tree = self.buildTree(size)
        self.inorder(head, tree)

        return tree