给一个sorted linked list，建一个balanced BST。 也是leetcode的原题 109 这题是1年前找实习的时候做的，没太大印象了。. From 1point 3acres bbs 在不考虑递归占用的空间复杂度的情况下， 我先给了一个把linked list转换成array的解法 O(n)时间复杂度 O(n)空间复杂度.鏈枃鍘熷垱鑷�1point3acres璁哄潧 又给了一个不转换成array的 O(nlogn)解法 O(1) 空间复杂度 做完两个解法之后大概还有20分钟。 小哥问我能不能再优化一点。 O(n) + O(1) 当时没想出来，面试结束后看了看leetcode的讨论，是用一种类似于inorder traversal的方式。 有兴趣的同学们点开下面的链接就好了。

109.Convert Sorted List to Binary Search Tree

Given 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.

Given the sorted linked list: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
      0
     / \
   -3   9
   /   /
 -10  5

Method 1 Bottom up Recursion, O(n) time O(log n) space.

• Essentially we can do a inorder traversal once we know the total length of the linked list.
• The recursive stack needs to maintain a space of log n.
• This is O(n) runtime because we are traversing the linked list 2 times.

class Solution(object):
    head = None
    def sortedListToBST(self, head):
        self.head = head
        runner = head
        count = 0
        while runner:
            count += 1
            runner = runner.next
        return self.helper(count)
    def helper(self, n):
        if n == 0:
            return None
        left = self.helper(n/2)
        root = TreeNode(self.head.val)
        root.left = left
        self.head = self.head.next
        root.right = self.helper(n - n/2 - 1)
        return root