C++实现LeetCode(108.将有序数组转为二叉搜索树)

C++实现LeetCode(108.将有序数组转为二叉搜索树)攻略

题目描述

给定一个有序整数数组,转换为高度平衡的二叉搜索树。

示例 1:

输入: [-10,-3,0,5,9]
输出: 
     0
    / \
  -3   9
  /   /
-10  5

示例 2:

输入: [1,3]
输出: 
  3
 / 
1  

题目分析

这道题目需要将有序整数数组转换为二叉搜索树,要求转换后的二叉树是平衡的,即左右子树的高度差不超过1。我们不难想到,可以采用递归的方式,将有序整数数组从中间位置划分成左右两个子数组,然后将中间的元素作为根节点,左子数组递归构建为根节点的左子树,右子数组递归构建为根节点的右子树。

解题思路

为了构建高度平衡的二叉搜索树,我们需要在递归过程中保证左右子树的高度差不超过1。具体的实现过程如下:

1.首先定义递归函数treeNode* buildBST(vector<int> &nums, int left, int right),其中nums为有序整数数组,leftright分别为当前递归的区间左右端点。

2.递归终止条件为left > right时,返回NULL表示空节点。

3.找到当前区间的中间位置mid = (left + right) / 2,将中间元素作为根节点创建treeNode* root = new treeNode(nums[mid])

4.递归构建根节点的左子树root->left = buildBST(nums, left, mid - 1);和右子树root->right = buildBST(nums, mid + 1, right);

5.返回根节点return root;

代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return buildBST(nums, 0, nums.size() - 1);
    }

    TreeNode* buildBST(vector<int> &nums, int left, int right){
        if(left > right){
            return NULL;
        }
        int mid = (left + right) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = buildBST(nums, left, mid - 1);
        root->right = buildBST(nums, mid + 1, right);
        return root;
    }
};

示例说明

以示例1为例,输入数组[-10,-3,0,5,9],函数调用如下:

sortedArrayToBST([-10,-3,0,5,9])

即:

buildBST([-10,-3,0,5,9], 0, 4)
-> TreeNode(-3)
   /         \
NULL         TreeNode(9)
             /       \
     TreeNode(-10)  TreeNode(5)
            /          \
         NULL         NULL

所以输出结果是:

     0
    / \
  -3   9
  /   /
-10  5

以示例2为例,输入数组[1,3],函数调用如下:

sortedArrayToBST([1, 3])

即:

buildBST([1, 3], 0, 1)
-> TreeNode(3)
   /         \
TreeNode(1)  NULL
            /      
          NULL     

所以输出结果是:

  3
 / 
1  

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C++实现LeetCode(108.将有序数组转为二叉搜索树) - Python技术站

(0)
上一篇 2023年6月27日
下一篇 2023年6月27日

相关文章

  • Mysql 8.0解压版下载安装以及配置的实例教程

    MySQL 8.0解压版下载安装以及配置的实例教程 本教程将详细介绍如何下载、安装和配置MySQL 8.0解压版。MySQL是一个流行的开源关系型数据库管理系统,提供了稳定可靠的数据存储和管理功能。 步骤1:下载MySQL 8.0解压版 首先,访问MySQL官方网站(https://www.mysql.com/)并导航到下载页面。在下载页面中,找到MySQL…

    other 2023年8月15日
    00
  • 魔兽世界8.0冰法堆什么属性好 8.0冰法属性选择优先级及收益一览

    魔兽世界8.0冰法堆什么属性好 冰法在8.0版本后,属性选择和收益都有所不同。大部分属性选择至多两种,需要权衡利弊。以下是属性选择及其权重的顺序,以及每个属性的收益。 优先级和收益一览 智力:智力是冰法最重要的属性。提高智力可提高法术强度,增加法术暴击和精通。每提高1点智力,可以提升1点法术强度。智力的每1%会提高0.8%的法术暴击和精通。 急速:急速可以提…

    other 2023年6月27日
    00
  • bigdecimal创建初始化值类型对比

    Bigdecimal创建初始化值类型对比 简介 BigDecimal 是 Java 中一个用于精确计算的类,对于一些对计算精度要求比较高的场合,例如金(融)业务计算,非常有用。在 BigDecimal 类中,可以使用字符串、double、int 等多种类型来初始化一个 BigDecimal 对象,性能和精度也不同。本文将对比不同的初始化方式带来的性能和精度影…

    其他 2023年3月28日
    00
  • 关于angular浏览器兼容性问题的解决方案

    关于Angular浏览器兼容性问题的解决方案,可以采取以下步骤: 步骤一:使用polyfills 在Angular项目中,如果使用了Web APIs,比如IntersectionObserver、ResizeObserver,以及一些ECMAScript特性比如Promise、fetch,那么部分用户使用的浏览器可能不支持这些API和特性。 解决这个问题,可…

    other 2023年6月26日
    00
  • 苹果操作系统详解

    苹果操作系统详解 苹果操作系统是苹果公司开发的、运行于苹果电脑上的操作系统,主要包括macOS和iOS两个版本。macOS是苹果电脑上的操作系统,而iOS则是苹果公司的移动设备操作系统。 macOS操作系统 系统架构 macOS的核心是基于UNIX的Darwin内核。Darwin内核是开源的,因此开发者可以获得内核源代码、自主开发定制版内核。macOS还包括…

    其他 2023年4月16日
    00
  • Android context源码详解及深入分析

    Android Context源码详解及深入分析攻略 1. 什么是Android Context? 在Android开发中,Context是一个非常重要的概念。它代表了当前应用程序的运行环境,提供了访问应用程序资源和系统服务的接口。Context是一个抽象类,它的具体实现类是ContextImpl。 2. Context的主要功能 Context提供了许多重…

    other 2023年8月21日
    00
  • 关于配置:pgadmin4:无法联系postgresql应用程序服务器

    以下是关于配置pgAdmin4时遇到无法联系PostgreSQL应用程序服务器的完整攻略,包含两个示例。 关于配置pgAdmin时遇到无法联系PostgreSQL应用服务器的攻略 在配置Admin4时,有时候会遇到无法Post应用程序的问题。以下是两个示例: 1. 检查PostgreSQL服务器是否正在行 首先,我们需要检查PostgreSQL服务器是否正在…

    other 2023年5月9日
    00
  • Linux shell 提取文件名和目录名的方法

    Linux shell 中提取文件名和目录名的方法通常使用shell变量和一些特定命令。以下是提取文件名和目录名的几种方法: 使用$变量获取当前目录和文件名 在Linux shell中,我们可以使用一些特殊的变量获取当前目录和文件名。其中,$PWD变量表示当前目录的路径,$0变量表示当前脚本的文件名,$1变量表示脚本后的第一个参数(文件名)。 例如,我们可以…

    other 2023年6月26日
    00
合作推广
合作推广
分享本页
返回顶部