leecode刷题 将有序数组转换为二叉搜索树

简介: 给定一个升序排列的整数数组 `nums`,要求将其转换为一棵高度平衡的二叉搜索树(BST)。通过递归方法,选择数组中间元素作为根节点,左半部分构建左子树,右半部分构建右子树。优化后的代码使用索引递归,避免了数组复制操作,提高了效率。

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

示例 1:
image.png

输入:nums = [-10,-3,0,5,9]
输出:[0,-3,9,-10,null,5]
解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:

示例 2:
image.png

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

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 按 严格递增 顺序排列

我第一个方案是采用的数组截取的方式


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
import java.util.Arrays;

class Solution {
   
    public TreeNode sortedArrayToBST(int[] nums) {
   
        if (nums == null)
            return null;
        int mid = (nums.length) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        // left 0,mid-1,right mid+1,nums.lenght-1
        if (mid == 1) {
   
            root.left = new TreeNode(nums[0]);
        } else if (mid >= 2) {
   
            int[] leftnums = Arrays.copyOfRange(nums, 0, mid);

            root.left = sortedArrayToBST(leftnums);
        }
        if (mid == nums.length - 2) {
   
            root.right = new TreeNode(nums[nums.length - 1]);
        } else if (mid < nums.length - 2) {
   
            int[] rightnum = Arrays.copyOfRange(nums, mid + 1, nums.length);

            root.right = sortedArrayToBST(rightnum);
        }

        return root;

    }

}

这个方案AI优化后,认为可以通过索引的方式完成递归,以下为优化后的代码


public class Solution {
   
    public TreeNode sortedArrayToBST(int[] nums) {
   
        if (nums == null || nums.length == 0) {
   
            return null;
        }
        return buildBST(nums, 0, nums.length - 1);
    }

    private TreeNode buildBST(int[] nums, int start, int end) {
   
        if (start > end) {
   
            return null;
        }
        int mid = start + (end - start) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = buildBST(nums, start, mid - 1);
        root.right = buildBST(nums, mid + 1, end);
        return root;
    }
}
相关文章
|
1月前
|
Java 开发者 Spring
Java Springboot监听事件和处理事件
通过这些内容的详细介绍和实例解析,希望能帮助您深入理解Spring Boot中的事件机制,并在实际开发中灵活应用,提高系统的可维护性和扩展性。
63 7
|
程序员 开发工具 Windows
如果你有个程序员男友,那么送这12 款键盘绝对不会错
对于程序员而言电脑就是他们的用于挣面包的工具,也是他们生活中面对时间最长的东西,而对于写代码而言,键盘则是程序员的利器,程序员对于生活中很多事情可以都是凑合了事,但是对于电脑、键盘、鼠标这些却是不可能将就的,就像那句话“因为生命中出现了那把机械键盘,那么其他的键盘都成了将就,而我,不愿意将就”。
10053 1
|
测试技术 API 容器
云效测评之测试提效
业务发展过程中都会不可避免的面临服务增长,应用负责度增加,可持续测试的难度不断增加。对于测试团队而言,一方面要应对不断膨胀的测试用例,维护成本越来越高,开发效率开始降低。
850 0
云效测评之测试提效
|
8月前
|
弹性计算 缓存 监控
云效将项目代码部署到云服务器ECS
云效支持一键和手动部署,一键部署因其高效、一致性和可重复性而受青睐,但也存在灵活性不足和初期设置复杂的挑战。优化方向包括简化脚本、提供选项、完善文档、集成监控和回滚机制。一键部署步骤概括为:准备云效项目和ECS,配置项目和环境,编写部署脚本,设置一键部署,测试脚本,审核发布,监控结果,及后续维护。实际操作应参照云效最新文档。
|
存储 弹性计算 运维
阿里云acp考试题库介绍 阿里云ACP认证有没有用?
互联网时代如果你还不懂电脑知识,那你恐怕就落伍了,现在很多互联网公司都会招聘网站运维人员,如果你懂相关技术那么将来就业就会方便很多。想要应聘互联网运维岗位是需要有相关证书的,其中阿里云acp认证就是很多人都会去考的一种认证,因为阿里云市场占有率比较高,这也导致国内普遍比较认可阿里云acp认证。如果你打算报考阿里云acp认证,下面认证大使就来给大家介绍一下阿里云acp考试题库。
361 0
阿里云acp考试题库介绍 阿里云ACP认证有没有用?
|
3月前
|
人工智能 自动驾驶 大数据
预告 | 阿里云邀您参加2024中国生成式AI大会上海站,马上报名
大会以“智能跃进 创造无限”为主题,设置主会场峰会、分会场研讨会及展览区,聚焦大模型、AI Infra等热点议题。阿里云智算集群产品解决方案负责人丛培岩将出席并发表《高性能智算集群设计思考与实践》主题演讲。观众报名现已开放。
|
2月前
|
Python
使用pycharm 开发streamlit的项目启动
要在 PyCharm 中配置 Streamlit 环境并调试应用,请按以下步骤操作:1. 确保 PyCharm 配置了 Python 解释器并安装 Streamlit 包(File -&gt; Settings -&gt; Project -&gt; Python Interpreter)。2. 配置调试运行设置(Run -&gt; Edit Configurations,添加 Python 配置并命名)。3. 选择新配置并点击调试按钮启动应用。
118 23
|
6月前
|
Web App开发
Chrome 126版本 打印预览失败 #85
Chrome 126版中出现了打印预览功能失效的问题(#85)。目前有两种解决方案:一是在chrome.exe目录为“ALL APPLICATION PACKAGES”用户组设置适当权限;二是等待内核修复,或通过添加启动参数&quot;--disable-features=PrintCompositorLPAC&quot;来暂时解决此问题。
878 1
|
2月前
|
存储 前端开发 数据可视化
百炼+魔笔,极速开发端到端的大模型应用
随着大模型技术的不断进步,应用创新呈现出蓬勃发展的势头。开发者在基于百炼完成智能体开发后往往还需要解决应用正式生产上线相关的一系列工程性问题,本文介绍如何通过百炼 + 多端低代码开发平台魔笔的云产品组合的方式快速构建一个端到端的大模型应用,为AI创新加码提速。
|
7月前
|
人工智能 自然语言处理 算法
创作吧开发者第三期:AI的奇思妙想之旅
从认识AI算法到使用AI工具再进阶为算法性能提升,不知不觉中,AI智能家居与私人助手成为了最熟悉我们生活的小助理。此外,文学、美术及音乐的联动,AI的创意作品也给我们带来更多的想象。 快来用文字为AI记录成长轨迹,用想象探索AI的无限奥秘,让灵感在字里行间流淌,你的每一个想法和记录都会成为AI浩瀚宇宙中的星辰!期待与各位创意满满且热爱创作的你们,共赴一场AI的奇思妙想之旅!
659 25

热门文章

最新文章