【算法题】108. 将有序数组转换为二叉搜索树

这篇具有很好参考价值的文章主要介绍了【算法题】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] 都是高度平衡二叉搜索树。

提示:

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

题解

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }

    public TreeNode helper(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }

        // 总是选择中间位置左边的数字作为根节点
        int mid = (left + right) / 2;

        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, left, mid - 1);
        root.right = helper(nums, mid + 1, right);
        return root;
    }
}

来自力扣官方题解文章来源地址https://www.toymoban.com/news/detail-829424.html

到了这里,关于【算法题】108. 将有序数组转换为二叉搜索树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣日记1.14-【二叉树篇】108. 将有序数组转换为二叉搜索树

    日期:2023.1.14 参考:代码随想录、力扣 题目描述 难度:简单 给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 示例 1: 输入:

    2024年02月01日
    浏览(39)
  • 第23天-代码随想录刷题训练-第六章 ● 669. 修剪二叉搜索树 ● 108.将有序数组转换为二叉搜索树 ● 538.把二叉搜索树转换为累加树

    - LeetCode 链接 给你二叉搜索树的根节点 root ,同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树,使得所有节点的值在[low, high]中。 修剪树不应该改变保留在树中的元素的相对结构 (即,如果没有被移除,原有的父代子代关系都应当保留)。 可以证明,存在唯一的答案

    2024年02月05日
    浏览(42)
  • 力扣 108 将有序数组转化为二叉搜索树

    目录 题目描述: 代码部分: (1)第一种方法  (2)第二种方法 题目解析: (1)复杂度与思想 (2)进阶分析: 给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高

    2024年02月08日
    浏览(35)
  • 算法刷题Day 23 修剪二叉搜索树+将有序数组转换为二叉搜索树+把二叉搜索树转换为累加树

    递归 好神奇,完全凭感觉写,感觉应该过不了,结果就过了 具体是什么原理可以参考代码随想录的讲解 递归 迭代 使用三个队列来处理(感觉用三个栈也可以) 其实就是以右-中-左的顺序来处理二叉树 每次将当前节点加上上一次访问节点的新值 能想到保存前一次访问节点的

    2024年02月15日
    浏览(41)
  • HOT42-将有序数组转换为二叉搜索树

          leetcode原题链接 :将有序数组转换为二叉搜索树        上一篇 :HOT41-二叉树的层序遍历       下一篇 :HOT43-验证二叉搜索树         给你一个整数数组  nums  ,其中元素已经按  升序  排列,请你将其转换为一棵  高度平衡  二叉搜索树。 高度平衡  二叉树是一

    2024年02月12日
    浏览(39)
  • 将有序数组转换为二叉树

    md这个破CSDN模板怎么没了,编辑器也死难用,气死 给你一个整数数组  nums  ,其中元素已经按  升序  排列,请你将其转换为一棵  高度平衡  二叉搜索树。 高度平衡  二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 示例 1: 示例 2:

    2024年02月05日
    浏览(37)
  • ( “树” 之 BST) 109. 有序链表转换二叉搜索树 ——【Leetcode每日一题】

    二叉查找树(BST):根节点大于等于左子树所有节点,小于等于右子树所有节点。 二叉查找树中序遍历有序。 给定一个单链表的头节点 head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子

    2023年04月23日
    浏览(39)
  • 力扣0109——有序链表转换二叉搜索树

    难度: 中等 给定一个单链表的头节点 head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。 输入: head = [-10,-3,0,5,9] 输出: [0,-3,9,-10,null,5] 解释: 一个可能的答案是[0,-

    2024年02月21日
    浏览(37)
  • OJ练习第137题——有序链表转换二叉搜索树

    力扣链接:109. 有序链表转换二叉搜索树 给定一个单链表的头节点 head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。 来源:力扣(LeetCode) 链接:https://leetcode.cn/

    2024年02月16日
    浏览(33)
  • LeetCode面试算法-力扣 88. 合并两个有序数组

    88. 合并两个有序数组 题目描述     给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意: 最终,合并后数组不应由函数返回,而是存储

    2024年02月10日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包