Cocolib

Appearance

On this page

将有序数组转换为二叉搜索树 ​

Question

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足 每个节点的左右两个子树的高度差的绝对值不超过 1 的二叉树。

image-20230614152826460

思路 ​

**高度平衡的实现思路：**取有序数组的最中间的值作为根节点

js
var sortedArrayToBST = function(nums) {
    if(nums.length===0) return null			//终止条件
    let root = new TreeNode()
    let mid = Math.floor(nums.length/2)     //js 中"/"结果不是整数，是浮点数
    root.val = nums[mid]
    root.left = sortedArrayToBST(nums.slice(0,mid))
    root.right = sortedArrayToBST(nums.slice(mid+1,nums.length))
    return root
};