Day192:将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

[Genzhen]

每日一题会在下午四点在交流群集中讨论，五点小程序中更新答案 欢迎大家在下方发表自己的优质见解 二维码加载失败可点击 小程序二维码

扫描下方二维码，收藏关注，及时获取答案以及详细解析，同时可解锁800+道前端面试题。

[GuoLizhi]

使用递归求解，时间复杂度O(n), 空间复杂度O(n)

function TreeNode(val, left = null, right = null) {
    this.val = val
    this.left = left
    this.right = right
}
// 转化为二分搜索树
function buildBST(arr = []) {
    return _buildBST(arr, 0, arr.length - 1)
}

function _buildBST(arr = [], left, right) {
    const len = right - left + 1
    console.log(left, right)
    // 临界条件判断，只有一个节点
    if (left === right) {
        return new TreeNode(arr[left])
    } else if (left > right) {
        return null
    }
    const mid = Math.floor(left + (right - left) / 2)
    const root = new TreeNode(arr[mid])
    root.left = _buildBST(arr, left, mid - 1)
    root.right = _buildBST(arr, mid + 1, right)
    return root
}