这道题忍不住写个博客记录一下第一次接触二叉搜索树的自己。。。在那里找个例子手动演示代码过程的时候，被自己的愚蠢成功的逗笑了。。。写博客的时候也忍不住的想笑。。。
方法一：递归
官方题解之一
先来分析一下题目描述，
首先题目给定的这个 单链表中的元素是按升序排序的，这就大大降低的题目难度；
其次，题目要求我们将该升序单链表转换为一个高度平衡的二叉搜索树，这就意味着，我们每次都只需要找到中间节点即可。
所谓高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。
一颗二叉搜索树是一颗有根二叉树并且对于所有节点满足特殊性质：
对于树中任意一个点，它的权值必然>=所有左子树节点的权值，<=所有右子树节点的权值。
因为二叉树具有递归的子结构，二叉搜索树也同理：所有子树也是二叉搜索树。
方法一的主要思路：
给定列表总的中间元素将会作为二叉搜索树的根，该点左侧的所有元素递归的去构造左子树，同理右侧的元素构造右子树。这必然能保证最后构造出的二叉搜索树是平衡的。
算法：
- 1.由于我们得到的是一个有序链表而不是数组，我们不能直接使用下标来访问元素。我们需要知道链表中的中间元素。
- 2.（Q1_为什么这样就可以访问到中间节点了？）我们可以利用两个指针来访问链表中的中间节点。假设我们有两个指针slow_ptr和fast_ptr.
- slow_ptr每次向后移动一个节点
- fast_ptr每次向后移动两个节点
- 当fast_ptr到达链表的末尾时，slow_ptr就访问到链表的中间元素。
- 对于一个偶数长度的数组，中间两个元素都可用来做二叉搜索树的根
- 3.当找到链表中的中间元素后，我们将链表从中间元素的左侧断开，做法是使用一个prev_ptr的指针记录slow_ptr之前的元素，也就是满足prev_ptr.next = slow_ptr。断开左侧部分就是让prev_ptr.next = None。
- 4.我们只需要将链表的头指针传递给转换函数，进行高度平衡二叉搜索树的转换。所以递归调用的时候，左半部分我们传递原始的头指针 ；右半部分传递slow_ptr.next作为头指针。
以官方题解给的样例为例吧，
理解了演示过程之后代码就很好写啦
方法一的代码：
#coding:utf-8
# 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 findMiddle(self, head):
prevPtr = None
slowPtr = head
fastPtr = head
while fastPtr and fastPtr.next:
prevPtr = slowPtr
slowPtr = slowPtr.next
fastPtr = fastPtr.next.next
if prevPtr:
prevPtr.next = None
return slowPtr
def sortedListToBST(self, head: ListNode) -> TreeNode:
if not head:
return None
mid = self.findMiddle(head)
node = TreeNode(mid.val)
if head == mid:
return node
node.left = self.sortedListToBST(head)
node.right = self.sortedListToBST(mid.next)
return node
说一下我自己在理解官方题解时蠢在了那里，我在看代码的时候不明白为啥要有这一步
然后自己手动演示的时候，到处理左半部分的时候我每次都是把整个链表传进去，发现咦，这不是死循环了么，去认真看了一遍算法的解析过程之后把自己的死循环解开了，这一步的作用也知道了。
这一步是为了断开链表的两侧，准确来说是左半部分。然后我就忍不住笑了。。。应该木有跟我一样的人了。。。
