Convert Sorted Array to Binary Search Tree

2019-02-25 16:10:59来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    if(!nums.length) return null;
    const result = new TreeNode(nums)
    return result
};

function TreeNode(nums) {
    if(nums.length){
        const middleIndex = Math.floor(nums.length/2)
        this.val = nums[middleIndex];
        if(middleIndex>0){
             this.left =  new TreeNode(nums.slice(0, middleIndex));
        } else {
             this.left =  null
        }
        if(middleIndex<nums.length-1){
            this.right = new TreeNode(nums.slice(middleIndex+1));
       } else {
           this.right = null
       }
    } else { return null }
}

上面是将有序数组转为二叉树的代码~

二分查找的速度为O(log n), 遍历二叉树的速度为O(n)


原文链接:https://www.cnblogs.com/yadiblogs/p/10422225.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:浅谈js抽象工厂模式

下一篇:原生 JS 的 Base64 转码