108. Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

使用递归,每次都取中点,作为当前部分的根节点,然后左边的部分作为其左子树,右边的部分作为其右子树
下面的两个方法一样的,一个使用了帮助函数一个没有。

var sortedArrayToBST = function(nums) {
    var help = function(left,right){
        if (left>right)
            return null;
        var mid = left+parseInt((right-left)/2);
        var node = new TreeNode(nums[mid]);
        var leftn = help(left,mid-1);
        var rightn = help(mid+1,right);
        if (leftn) 
            node.left = leftn;
        if (rightn)
            node.right = rightn;
        return node;
    };
    return help(0,nums.length-1);
};
var sortedArrayToBST = function(nums) {
    var len = nums.length;
    if (len!==0) {
        var mid = parseInt(len/2);
        var node = new TreeNode(nums[mid]);
        var left = sortedArrayToBST(nums.slice(0,mid));
        var right = sortedArrayToBST(nums.slice(mid+1,len));
        if (left) 
            node.left = left;
        if (right)
            node.right = right;
        return node;
    }
    return null;
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容