21_链表_109. 有序链表转换二叉搜索树.md

-- 链表 - mid 点击直达力扣

给定一个单链表的头节点 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

// 首先遍历链表，将链表的值存储在数组里面
// 以中间数作为根节点，左边为左子树，右边为右子树
// 递归，直到left > right
function sortedListToBST(head: ListNode | null): TreeNode | null {
    if (!head) { return null }

    let nodeArr = []
    while (head) {
        nodeArr.push(head.val)
        head = head.next
    }

    function bst(left: number, right: number) {
        if (left > right) { return null }
        const mid = left + Math.floor((right - left) / 2)
        const root = new TreeNode(nodeArr[mid])
        root.left = bst(left, mid - 1)
        root.right = bst(mid + 1, right)
        return root
    }

    return bst(0, nodeArr.length - 1)
};