108. 将有序数组转换为二叉搜索树
108. 将有序数组转换为二叉搜索树
🟢 🔖 树
二叉搜索树
数组
分治
二叉树
🔗 力扣
LeetCode
题目
Given an integer array nums
where the elements are sorted in ascending order , convert it to a ** height-balanced** binary search tree.
Example 1:
Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:
Example 2:
Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.
Constraints:
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums
is sorted in a strictly increasing order.
题目大意
给你一个整数数组 nums
,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
解题思路
可以通过递归地选择数组中间元素构建树的节点:
- 选择数组中间的元素作为当前节点的值,确保左右子树的节点数量相近,从而实现高度平衡。
- 递归地处理左右子数组,分别构建左右子树。
- 对于每个子数组,重复步骤 1 和步骤 2,直到子数组为空。
- 返回根节点,即整棵高度平衡的二叉搜索树。
代码
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var sortedArrayToBST = function (nums) {
if (!nums.length) return null;
// 选择中间元素作为当前节点
const mid = Math.floor(nums.length / 2);
let root = new TreeNode(nums[mid]);
// 递归构建左右子树
root.left = sortedArrayToBST(nums.slice(0, mid));
root.right = sortedArrayToBST(nums.slice(mid + 1));
return root;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
109 | 有序链表转换二叉搜索树 | [✓] | 树 二叉搜索树 链表 2+ |