- 分类：LinkList/Tree
- 时间复杂度: O(nlogn) 因为每次都需要遍历linklist的一半
- 空间复杂度: O(h) 树的节点的深度
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.
Example:
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
代码：
# 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 sortedListToBST(self, head: 'ListNode') -> 'TreeNode':
# 没有或者只有一个数的时候
if head==None:
return None
if head.next==None:
return TreeNode(head.val)
# 有两个数以上的时候
slow,fast=head,head
prev=None
while fast and fast.next:
prev=slow
slow=slow.next
fast=fast.next.next
prev.next=None
root=TreeNode(slow.val)
root.left=self.sortedListToBST(head)
root.right=self.sortedListToBST(slow.next)
return root
讨论：
1.一看之下感觉和108很像，后来发现是linklist，就又不会做了=。=于是在youtube上找到了公瑾讲解
2.这道题考察了linklist和树的操作
3.找linklist的中位数可以用fast/slow指针去找，每次fast走两格，slow走一格，当fast走完的时候slow刚好走到了中间
4.边界条件其实也很难，一定要注意，当没有数和只有一个数的时候是边界条件，直接退出即可，只有linklist有两个数+的时候才开始找中位数做题。
