Appearance
109. 有序链表转换二叉搜索树
题目描述
给定一个单链表的头节点 head ，其中的元素 按升序排序 ，将其转换为 平衡 二叉搜索树。
示例 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
难度： Medium
题解代码
javascript
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {ListNode} head
* @return {TreeNode}
*/
var sortedListToBST = function(head) {
const arr = []
let p = head
while (p) {
arr.push(p.val)
p = p.next
}
return sortedArrayToBST(arr, 0, arr.length - 1)
};
function sortedArrayToBST (nums, start, end) {
if (start > end) return null
const mid = Math.floor((start + end) / 2)
const node = new TreeNode(nums[mid])
node.left = sortedArrayToBST(nums, start, mid - 1)
node.right = sortedArrayToBST(nums, mid + 1, end)
return node
}