原题
给出一个所有元素以升序排序的单链表，将它转换成一棵高度平衡的二分查找树
解题思路
- 跟二叉树相关 - 分治法，递归求解
- 链表问题，有序链表，如果将节点中的所有值都存入数组，本题目可以转化为Convert Sorted Array to Binary Search Tree，时间复杂度是O(n)，前序构建二叉树
- 数组访问任意一个元素时间复杂度是O(1)，而链表不行。如果在链表上每次查找中点，总时间复杂度O(nlogn)
- 构建树的层数 - logn
- 每一次找中点 - O(n)
- 另外一种优化O(nlogn) => O(n)，因为对于BST来说，中序遍历的结果就是一个从小到大的有序序列。所以尝试通过遍历一个有序的linked list，利用类似中序遍历的方式构建BST。从下到上构建这棵树，用一个current变量记录链表的当前节点。sortedListToBSTHelper的定义是：将current指针开头的，从start到end的linked list转变为BST，每次current指针指向下一个node。
完整代码
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def sortedListToBST(self, head):
"""
:type head: ListNode
:rtype: TreeNode
"""
self.current = head
size = self.getListLength(head)
return self.sortedListToBSTHelper(size)
def getListLength(self, head):
size = 0
while head:
size += 1
head = head.next
return size
def sortedListToBSTHelper(self, size):
if size <= 0:
return None
left = self.sortedListToBSTHelper(size / 2)
root = TreeNode(self.current.val)
self.current = self.current.next
right = self.sortedListToBSTHelper(size - 1 - size / 2)
root.left = left
root.right = right
return root
