【算法】leetcode 108. 将有序数组转换为二叉搜索树（及相关算法扩展)

题目

下面为从一个随机数组转换为一个二叉查找树，在通过中序遍历得到升序数组的（108题的输入），通过相关算法将升序数组转换为高平衡的二叉搜索树。因为js得到的是个对象和题目输出的数组不符，观察发现108题输出的为层序遍历的结果，通过102题层序遍历的转换得到结果。

// 树节点结构
function TreeNode(value, left, right) {
    this.value = (value === undefined ? 0 : value)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
}
// 二叉搜索树：插入节点
function InsertNode(root, key) {
    if (!root.value) {   //如果根结点不存在，则建立根结点
        root.value = key;
        return true;
    }
    if (root.value > key) {  //当前结点值比插入值大，说明插入位置在当前结点值的左子树中
        if (root.left) {  //如果有左孩子结点，继续比较
            InsertNode(root.left, key);
        } else {   //插入操作
            root.left = new TreeNode(key);
        }
    } else if (root.value < key) { //当前结点值比插入值小，说明插入位置在当前结点值的右子树中
        if (root.right) { //如果有右孩子结点，继续比较
            InsertNode(root.right, key);
        } else {  //插入操作
            root.right = new TreeNode(key);
        }
    } else {  //树中已存在插入值的结点
        return false;
    }
    return true;
}
// 创建二叉查找树
function createTree(array) {
    var tree = new TreeNode(null);  //建立根节点
    for (let i = 0; i < array.length; i++) {
        InsertNode(tree, array[i]);
    }
    return tree;
}

// let treeArr = [10, -5, 3, 18, 6]
// let treeArr = [-10, -3, 1, 5, 9]
// 随机节点
let treeArr = [-10, 5, 9, -3, 1]
let trees = createTree(treeArr)
console.log('创建一个二叉查找树', trees)

// 中序遍历
let arr = []
function inOrder(root) {
    if (root == null) {
        return;
    }
    inOrder(root.left);
    arr.push(root.value)
    inOrder(root.right);
    return arr;
}

console.log('中序遍历产生一个升序数组：', inOrder(trees))

// 高度平衡的二叉搜索树
var sortedArrayToBST = function (nums) {
    // 由于数组是排序好的，因此一个思路就是将数组分成两半，一半是左子树，另一半是右子树
    // 然后运用“树的递归性质”递归完成操作即可。
    if (nums.length === 0) return null;
    const mid = nums.length >> 1;
    const root = new TreeNode(nums[mid]);

    root.left = sortedArrayToBST(nums.slice(0, mid));
    root.right = sortedArrayToBST(nums.slice(mid + 1))
    return root;
};
let sortedArray = sortedArrayToBST(arr)
console.log('产生一个高度平衡的二叉搜索树：',sortedArray)

//层序遍历
var levelOrder = function (root) {
    const ret = [];
    if (!root) {
        return ret;
    }
    // 队列
    const q = [];
    q.push(root);

    while (q.length !== 0) {
        const currentLevelSize = q.length;
        ret.push([]);
        for (let i = 1; i <= currentLevelSize; ++i) {
            const node = q.shift();
            ret[ret.length - 1].push(node.value);
            if (node.left) q.push(node.left);
            if (node.right) q.push(node.right);
        }
    }

    return ret;
};

console.log(levelOrder(sortedArray))

输出结果：