HOT42-将有序数组转换为二叉搜索树

这篇具有很好参考价值的文章主要介绍了HOT42-将有序数组转换为二叉搜索树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

      leetcode原题链接:将有序数组转换为二叉搜索树

      上一篇:HOT41-二叉树的层序遍历

      下一篇:HOT43-验证二叉搜索树

题目描述

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

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

示例 1:

HOT42-将有序数组转换为二叉搜索树,leetcode最热100题,leetcode,算法,数据结构,二叉树

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

HOT42-将有序数组转换为二叉搜索树,leetcode最热100题,leetcode,算法,数据结构,二叉树

示例 2:

HOT42-将有序数组转换为二叉搜索树,leetcode最热100题,leetcode,算法,数据结构,二叉树

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

提示:

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

解题方法:每次取有序数组的中间节点作为root节点,然后利用二叉树的先序遍历方法实现左右子树的构建。文章来源地址https://www.toymoban.com/news/detail-520833.html

C++代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 * 0 1 2 3
 * 0 1 2 3 4
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int n = nums.size();
        if (n <= 0) {
            return nullptr;
        }
        return buildBST(nums, 0, n - 1);
    }
    TreeNode* buildBST(vector<int>& nums, int left, int right) { //[left, right]
        if (left > right) {
            return nullptr;
        }
        int mid = (left + right) / 2;
        TreeNode* root = new TreeNode(nums[mid]); //取中间位置的值作为根节点的值
        if (!root) {
            return nullptr;
        }
        root->left = buildBST(nums, left, mid - 1); //左子树
        root->right = buildBST(nums, mid + 1, right);//右子树
        return root;
    }
};

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

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

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

相关文章

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

    给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 示例 1: 输入:nums = [-10,-3,0,5,9] 输出:[0,-3,9,-10,null,5] 解释:[0,-10,5,null,-3,nul

    2024年02月20日
    浏览(39)
  • 力扣日记1.14-【二叉树篇】108. 将有序数组转换为二叉搜索树

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

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

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

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

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

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

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

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

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

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

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

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

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

    2024年02月21日
    浏览(38)
  • Java算法_ 验证二叉搜索树(LeetCode_Hot100)

    题目描述: 给你一个二叉树的根节点 ,判断其是否是一个有效的二叉搜索树。root 有效 二叉搜索树定义如下: 节点的左子树只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 获得更多?算法思路:代码文

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

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

    2024年02月16日
    浏览(34)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包