32_将有序数组转换为平衡二叉搜索树

简介: 32_将有序数组转换为平衡二叉搜索树

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

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

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1:

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

示例 2:

输入:nums = [1,3]
输出:[3,1]
解释:[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
//给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。
//
// 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
//
//
//
// 示例 1:
//
//
//输入:nums = [-10,-3,0,5,9]
//输出:[0,-3,9,-10,null,5]
//解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:
//
//
//
// 示例 2:
//
//
//输入:nums = [1,3]
//输出:[3,1]
//解释:[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
//
//
//
//
// 提示:
//
//
// 1 <= nums.length <= 104
// -104 <= nums[i] <= 104
// nums 按 严格递增 顺序排列
//
// Related Topics 树 二叉搜索树 数组 分治 二叉树
// 👍 1463 👎 0
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * 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;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return traversal(nums, 0, nums.length - 1);
    }
    public TreeNode traversal(int[] nums, int left, int right) {
        if (left > right)
            return null;
        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = traversal(nums, left, mid - 1);
        root.right = traversal(nums, mid + 1, right);
        return root;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
相关文章
|
10月前
|
前端开发 UED 开发者
React 对话框组件 Dialog
本文详细介绍了如何在 React 中实现一个功能完备的对话框组件(Dialog),包括基本用法、常见问题及其解决方案,并通过代码案例进行说明。从安装依赖到创建组件、添加样式,再到解决关闭按钮失效、背景点击无效、键盘导航等问题,最后还介绍了如何添加动画效果和处理异步关闭操作。希望本文能帮助你在实际开发中更高效地使用 React 对话框组件。
365 75
|
12月前
|
NoSQL Java 关系型数据库
阿里 P7二面:Redis 执行 Lua,到底能不能保证原子性?
Redis 和 Lua,两个看似风流马不相及的技术点,为何能产生“爱”的火花,成为工作开发中的黄金搭档?技术面试中更是高频出现,Redis 执行 Lua 到底能不能保证原子性?今天就来聊一聊。 
384 1
|
SQL Oracle 关系型数据库
SQL 面试系列(一)【留存率问题】
SQL 面试系列(一)【留存率问题】
|
12月前
|
JavaScript 搜索推荐 UED
vue的自定义指令
【10月更文挑战第14天】Vue 自定义指令为我们提供了一种强大的工具,使我们能够更灵活地控制和扩展 Vue 应用的行为。通过合理地使用自定义指令,可以提高开发效率,增强应用的功能和用户体验。
|
Dart JavaScript 前端开发
flutter-web中使用js工具类
flutter-web中使用js工具类
|
消息中间件 数据采集 移动开发
数仓建模—埋点设计与管理
开始之前我们先看一下我们为什么要收集埋点数据,埋点都可以做什么,埋点主要用于记录用户行为,几乎是应用必不可少的功能.埋点的作用包括但不限于
1276 0
数仓建模—埋点设计与管理
|
JavaScript 前端开发
深入理解 ECMAScript modules:提升你的 JavaScript 技能(二)
深入理解 ECMAScript modules:提升你的 JavaScript 技能(二)
|
存储 SQL 缓存
《MySQL高级篇》八、索引优化与查询优化(五)
《MySQL高级篇》八、索引优化与查询优化
《MySQL高级篇》八、索引优化与查询优化(五)
|
机器学习/深度学习 传感器 算法
基于遗传算法的柔性车间调度优化研究附Matlab代码
基于遗传算法的柔性车间调度优化研究附Matlab代码
|
Java
Java抽象
Java抽象
147 0
Java抽象