JavaScript 算法每日一题：将有序数组转换为二叉搜索树

大家好，欢迎来到IT知识分享网。

大家好，很高兴又见面了，我是姜茶的编程笔记，我们一起学习前端相关领域技术，共同进步，也欢迎大家关注、点赞、收藏、转发，您的支持是我不断创作的动力

铁子们！从 2024/07/26 开始，我们进入算法专题篇的学习啦 。学习计划如下：

1️⃣ 每日一题;

2️⃣ 学习顺序是由易到难；

3️⃣ 题目按照数据结构进行分类;

4️⃣ 每个类型的题目预计安排 100 道题（简单/中等/困难各 33 道）;

题目描述

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

示例 1：

示例 2：

输入： nums = [1,3]
输出： [3,1]
解释： [1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums 按 严格递增 顺序排列

一张图

分析/求解

要解决这个问题，我们可以利用二叉搜索树的特性，将数组的中间元素作为根节点，左右两边分别作为左右子树。以下是详细的解释和解法：

方法一：递归构建树

通过递归地选择数组的中间元素作为根节点，并对左右子数组重复该过程，最终得到平衡二叉搜索树。

• 时间复杂度：O(n)，其中 n 是数组的长度。我们需要访问数组中的每个元素。
• 空间复杂度：O(log n)，递归调用栈的深度为树的高度，最坏情况下为 O(log n)。

var sortedArrayToBST = function (nums) { if (nums.length === 0) { return null; } const mid = Math.floor(nums.length / 2); const root = new TreeNode(nums[mid]); // 递归地将数组的左半部分转换为左子树 root.left = sortedArrayToBST(nums.slice(0, mid)); // 递归地将数组的右半部分转换为右子树 root.right = sortedArrayToBST(nums.slice(mid + 1)); return root; }

总结

在实际应用中，递归构建树是解决这个问题的最佳选择，因为它不仅能在 O(n) 的时间复杂度内高效生成平衡二叉搜索树，而且实现简单易懂。欢迎大家提供其他思路哈。

最后

如果有任何问题或建议，欢迎在评论区留言交流！祝你编程愉快！