【链表Linked List】力扣-109 有序链表转换二叉搜索树
目录
题目描述
解题过程
官方题解
题目描述
给定一个单链表的头节点 head ，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。
示例 1:
输入: head = [-10,-3,0,5,9] 输出: [0,-3,9,-10,null,5] 解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。
示例 2:
输入: head = [] 输出: []
提示:
head中的节点数在[0, 2 * 104]范围内-105 <= Node.val <= 105
解题过程
不知道有没有人和我一样，有点抗拒树这种结构，但还是努力学习一下吧，可能熟悉了以后就会觉得这是一个很好的工具，┭┮﹏┭┮
读过题目后，第一想法是快慢指针，找到树的中间节点，使用递归结构，具体细节实现如下：
这是模仿前面做过的数组转二叉树做的，提示执行出错：
去搜索了一下问题出现的原因，解答如下： python默认递归调用深度为1000，程序运行过程中超过最大的递归深度，因此检查了一下代码，看是否存在死循环情况。但也没有发现什么问题，大概率是我对链表转二叉树操作不了解，直接学习解析吧，看看是否能发现问题所在。
官方题解
还是比较开心的，对比了官方题解后，大体思路没错，就是一些边界出错了，然后照着修改了一下，如下：
结果：
