将有序数组转换为平衡二叉搜索树（递归解法)

待我称王封你为后i 2023-01-01 02:55 124阅读 0赞

**解题思路**  
形成一颗平衡二叉搜索树的关键在于保证左右两子树高度差不大于1，也就是根节点为对应树的中位数，这里提供一个取两值中间整数的写法（a+b) >>> 1,将和向右无符号移动1位即为两者中位整数，当然也可以用Math.floor((a+b)/2)的写法，也是可以的

**代码**

/**
     * 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) {
        const buildBST = (nums, start, end) => {
            if(start > end) {
                return null;
            }
            const midIndex = (start + end) >>> 1;
            const root = new TreeNode(nums[midIndex]);
            root.left = buildBST(nums, start, midIndex - 1);
            root.right = buildBST(nums, midIndex + 1, end);
            return root;
        }
        return buildBST(nums, 0, nums.length - 1);
    };

小伙伴们今天的学习就到这里了，如果觉得本文对你有帮助的话，欢迎转发，评论，收藏，点赞！！！  
       每天学习进步一点点，就是领先的开始。如果想继续提高，欢迎关注我，或者关注公众号”祯民讲前端“。大量前端技术文章，面试资料，技巧等助你更进一步！  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhb2ZhbmRlZGFpbWE_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhb2ZhbmRlZGFpbWE_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/518b14ddc7ce4cc0b91abde7407105c1.png