108.将有序数组转成二叉搜索树

function TreeNode(val, left, right) {
    this.val = (val === undefined ? 0 : val)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
}

/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
// 此解法只能得到二叉搜索树，不能得到高度平衡二叉树。应使用递归找中间点为根节点不断分割左右子树
var sortedArrayToBST = function (nums) {
    // 先找到nums的中点，将nums分为左右子树，中点即为根节点
    const mid = Math.floor(nums.length / 2)
    const root = new TreeNode(nums[mid])

    // 遍历nums往root插入节点
    // 注意：这种插入解法符合二叉搜素树，但是不符合高度平衡二叉树
    // 高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
    // 举例：输入[0,1,2,3,4,5]，这种解法的结果[3,0,4,null,1,null,5,null,2]，左子树有两棵子树高度差大于1了。
    for (let i = 0; i < nums.length; i++) {
        if (i !== mid) {
            // 插入节点,bst二叉树：左节点<父节点<右节点
            let newNode = new TreeNode(nums[i])
            let cur = root
            while (true) {
                if (newNode.val < cur.val) {
                    if (cur.left === null) {
                        cur.left = newNode
                        break
                    }
                    cur = cur.left
                } else {
                    if (cur.right === null) {
                        cur.right = newNode
                        break
                    }
                    cur = cur.right
                }
            }
        }
    }

    return root
};

/**
 * 层序遍历
 * @param {TreeNode} root 
 */
function levelOrder(root) {
    let queue = [] // 每一层的节点
    queue.push(root) // 第一层
    let res = []

    while (queue.length > 0) {
        let len = queue.length // 当前层节点数
        // 遍历每一层，取出节点
        for (let i = 0; i < len; i++) {
            let node = queue.shift() // node有可能为null
            res.push(node ? node.val : null)
            // 添加下一层的节点到队列
            if (node) {
                queue.push(node.left)
                queue.push(node.right)
            }
        }
    }

    return res
}

/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function (nums) {
    // 先找到nums的中点，将nums分为左右子树，中点即为根节点
    // 再从左子树和右子树的nums里分别找到左子树的根节点和右子树的根节点，同理中点即为根节点
    // 再从分出的更小的左子树和右子树里找根节点
    // ......
    // 以此类推，其实是一个递归的过程

    if (!nums.length) { // 递归结束条件
        return null
    }

    const mid = Math.floor(nums.length / 2)
    const root = new TreeNode(nums[mid])
    let leftNums = nums.slice(0, mid) // 左子树的节点
    let rightNums = nums.slice(mid + 1) // 右子树的节点
    root.left = sortedArrayToBST(leftNums) // root的左节点即为左子树的根节点
    root.right = sortedArrayToBST(rightNums) // root的右节点即为右子树的根节点

    return root
}

// let root = sortedArrayToBST([-10, -3, 0, 5, 9])
let root = sortedArrayToBST([0, 1, 2, 3, 4, 5])
console.log(levelOrder(root))