题目描述（中等难度）

和 108 题是一样的，都是给定一个升序序列，然后生成二分平衡查找树。区别在于 108 题给定的是数组，这里给的是链表。

解法一

大家先看一下 108 题吧，算法的关键是取到中间的数据做为根节点。而这里链表的话，由于不支持随机访问，所以会麻烦些。最简单的思路就是我们把链表先用线性表存起来，然后题目就转换成 108 题了。

为了方便，把上一道题的数组参数改为。

时间复杂度：O(n)。

空间复杂度：数组进行辅助，O(n)。

参考这里。

有没有一种方案，不用数组的辅助呢？那么我们需要解决怎么得到 mid 的值的问题。

这里有一个求中点节点值的技巧，利用快慢指针。

快指针和慢指针同时从头部开始遍历，快指针每次走两步，慢指针每次走一步，当快指针走到链表尾部，此时慢指针就指向了中间位置。

除了求中点节点的值不一样，基本架构和是一样的。

时间复杂度：根据递归式可知，T(n) = 2 * T（n / 2 ) + n，。

空间复杂度：O(log(n))。

解法二虽然没有借助数组，优化了空间复杂度，但是时间复杂度增加了，那么有没有一种两全其美的方法，时间复杂度是解法一，空间复杂度是解法二。还真有，参考 -space-and-O(n)-time-Java-code>)。

主要思想是，因为我们知道题目给定的升序数组，其实就是二叉搜索树的中序遍历。那么我们完全可以按照这个顺序去为每个节点赋值。

先回想一下中序遍历的算法。

之前是将 node.val 进行保存，这里的话我们是给当前节点进行赋值，为了依次赋值，我们需要一个cur指针指向给定的数列，每赋一个值就进行后移。

时间复杂度：，主要是得到开始的 end，需要遍历一遍链表。

空间复杂度：O(log(n))，递归压栈的消耗。

快慢指针求链表的中间值，这个技巧不错。此外，解法三的模仿中序遍历的过程，然后把给定的数组依次赋值过去，太强了。

添加好友一起进步~

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击查看详情