108. Convert Sorted Array to Binary Search Tree
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:
![](https://assets.leetcode.com/uploads/2021/02/18/btree1.jpg)
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:
![](https://assets.leetcode.com/uploads/2021/02/18/btree.jpg)
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. 有序链表转换二叉搜索树](https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree)