题目
解题思路-基础
代码实现
解题思路-优化
代码实现
解题思路-进阶
代码实现
题目题目地址
给定一个单链表的头节点 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
本题要求我们将给定的有序链表转为高度平衡的二叉搜索树，所以我们要保证每个子树的左子树的值都比它小，右子树的值都比它大，同时高度差不超过1。
因为给定的链表是升序的，所以我们遍历链表节点将节点值存入数组，这样就得到了一个升序的数组。然后取数组的中间节点为根节点的值，左边的都是小于它的值，右边的都是大于它的值，再通过左右两边的数值去构造当前节点的左右子树。最后当所有值都处理完，就构造完成了一颗高度平衡的二叉搜索树。
代码实现var sortedListToBST = function(head) {
if(head === null){
return null
}
const list = []
while(head){
list.push(head.val)
head = head.next
}
function buildTree(list){
const len = list.length
if(len===0){
return null
}
const mid = len>>1
const nodeVal = list[mid]
const l = list.slice(0,mid)
const r = list.slice(mid+1)
return new TreeNode(nodeVal,buildTree(l),buildTree(r))
}
return buildTree(list)
};
解题思路-优化
上面的实现中我们每次都要切割 list 数组，其实可以更换为记录左右下标的方式，即省去了切割数组的过程，又不用每次创建子数组。
var sortedListToBST = function(head) {
if(head === null){
return null
}
const list = []
while(head){
list.push(head.val)
head = head.next
}
function buildTree(l,r){
if(l>r){
return null
}
const mid = (l+r)>>1
const nodeVal = list[mid]
return new TreeNode(nodeVal,buildTree(l,mid-1),buildTree(mid+1,r))
}
return buildTree(0,list.length-1)
};
解题思路-进阶
上面的实现方式时、空复杂度都是 O(nlogn) O(logn)，但是第二种做了进一步优化，实际表现会更好一点。 而下面的实现方式时、空复杂度为：O(n) O(logn)。
这里我们转换思路，不去首先构造根节点，而是采用中序遍历的顺序构造目标二叉树，这样构造的顺序就可以和遍历链表的顺序吻合，达到在遍历链表的过程完成构造二叉树。
代码实现const sortedListToBST = (head) => {
if (head == null){
return null
}
let len = 0
let cur = head
while (head) {
len++
head = head.next
}
function buildTree(l,r){
if (l > r){
return null
}
const mid = (l + r) >>> 1
const leftTree = buildTree(l, mid - 1)
const node = new TreeNode(cur.val)
node.left = leftTree
cur = cur.next
node.right = buildTree(mid + 1, r)
return node
}
return buildTree(0, len - 1)
};
至此我们就完成了 leetcode-109-有序链表转换二叉搜索树，更多关于前端算法有序链表转换二叉搜索树的资料请关注易知道(ezd.cc)其它相关文章！
