108. Convert Sorted Array to Binary Search Tree

🟢   🔖  树 二叉搜索树 数组 分治 二叉树  🔗 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. 递归地处理左右子数组，分别构建左右子树。
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. 有序链表转换二叉搜索树

- [109. 有序链表转换二叉搜索树](https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree)