跳至主要內容

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


108. 将有序数组转换为二叉搜索树open in new window

🟢   🔖  二叉搜索树 数组 分治 二叉树  🔗 力扣open in new window LeetCodeopen in new window

题目

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. 递归地处理左右子数组,分别构建左右子树。
  3. 对于每个子数组,重复步骤 1 和步骤 2,直到子数组为空。
  4. 返回根节点,即整棵高度平衡的二叉搜索树。

代码

/**
 * @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有序链表转换二叉搜索树open in new window[✓] 二叉搜索树 链表 2+