有序链表转换二叉搜索树」,难度为「中等」
Tag : 「二叉树」、「树的搜索」、「分治」、「中序遍历」
给定一个单链表的头节点 head,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树。...本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过
1
。...示例 1:
输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0,-3,9,-10,null,5],它表示所示的高度平衡的二叉搜索树...将有序数组转换为二叉搜索树 类似,但链表相对于数组,无法
O(1)
找到构建当前 BST 根节点的“中点”下标。...一个不使用
O(n)
空间复杂度的做法,需要每次遍历来找“中点”下标:起始我们先对 head 进行一次遍历,得到链表长度
n
,随后仍然利用递归分治的思路进行构造,每次对入参的左右端点找“中点”,