当前位置: 首页 > news >正文

【算法与数据结构】654、LeetCode最大二叉树

文章目录

  • 一、题目
  • 二、解法
  • 三、完整代码

所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

在这里插入图片描述
在这里插入图片描述

二、解法

  思路分析:【算法与数据结构】106、LeetCode从中序与后序遍历序列构造二叉树这两道题有些类似,相关代码可以互相参考,本题明示了要用递归来做,那么递归三要素不可缺少:输入参数和返回值;单层递归逻辑;终止条件。本题当中,输入参数引用二叉树遍历数组,同时根据最大值划分的边界[Begin, End),代码统一为左闭右开区间,区间具体如何划分设计到边界条件是否+1-1这种。返回值为root根节点。
  程序如下

class Solution {
public:// 3、输入参数TreeNode* traversal(const vector<int> &nums, int Begin, int End) {// 1、终止条件if (Begin == End) return NULL;//2、单层递归逻辑int maxIndex = Begin;for (int i = Begin; i < End; i++) { // 找最大值if (nums[i] > nums[maxIndex]) maxIndex = i;}TreeNode* root = new TreeNode(nums[maxIndex]);// 最大值左边部分,左闭右开[leftBegin, leftEnd)int leftBegin = Begin; int leftEnd = maxIndex;if (leftEnd < leftBegin) leftEnd = Begin;// 最大值右边部分,左闭右开[rightBegin, rightEnd)int rightBegin = maxIndex + 1;int rightEnd = End;if (rightBegin > rightEnd) rightBegin = End;root->left = traversal(nums, leftBegin, leftEnd);root->right = traversal(nums, rightBegin, rightEnd);// 3、返回值return root;}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {  if (!nums.size()) return NULL;return traversal(nums, 0, nums.size());}
};

三、完整代码

# include <iostream>
# include <vector>
# include <queue>
using namespace std;// 树节点定义
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) {}
};class Solution {
public:// 3、输入参数TreeNode* traversal(const vector<int> &nums, int Begin, int End) {// 1、终止条件if (Begin == End) return NULL;//2、单层递归逻辑int maxIndex = Begin;for (int i = Begin; i < End; i++) { // 找最大值if (nums[i] > nums[maxIndex]) maxIndex = i;}TreeNode* root = new TreeNode(nums[maxIndex]);// 最大值左边部分,左闭右开[leftBegin, leftEnd)int leftBegin = Begin; int leftEnd = maxIndex;if (leftEnd < leftBegin) leftEnd = Begin;// 最大值右边部分,左闭右开[rightBegin, rightEnd)int rightBegin = maxIndex + 1;int rightEnd = End;if (rightBegin > rightEnd) rightBegin = End;root->left = traversal(nums, leftBegin, leftEnd);root->right = traversal(nums, rightBegin, rightEnd);// 3、返回值return root;}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {  if (!nums.size()) return NULL;return traversal(nums, 0, nums.size());}
};// 层序遍历
vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()) {int size = que.size();  // size必须固定, que.size()是不断变化的vector<int> vec;for (int i = 0; i < size; ++i) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.push_back(vec);}return result;
}template<class T1, class T2>
void my_print2(T1& v, const string str) {cout << str << endl;for (class T1::iterator vit = v.begin(); vit < v.end(); ++vit) {for (class T2::iterator it = (*vit).begin(); it < (*vit).end(); ++it) {cout << *it << ' ';}cout << endl;}
}int main()
{//int arr[] = {3, 2, 1, 6, 0, 5};int arr[] = { 3, 2, 1};vector<int> nums(arr, arr + sizeof(arr) / sizeof(int));Solution s;TreeNode* root = s.constructMaximumBinaryTree(nums);vector<vector<int>> tree = levelOrder(root);my_print2<vector<vector<int>>, vector<int>>(tree, "目标树:");system("pause");return 0;
}

end

相关文章:

【算法与数据结构】654、LeetCode最大二叉树

文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引&#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析&#xff1a;【算法与数据结构】106、LeetCode从中序与后序遍历序列构造二叉树这两道题有些类似&#xff0c;相关代…...

您必须尝试的 4 种经典特征提取技术!

一、说明 特征提取如何实现&#xff1f;其手段并不是很多&#xff0c;有四个基本方法&#xff0c;作为AI工程师不能不知。因此&#xff0c;本篇将对四种特征提取给出系统的方法。 二、概述 图像分类长期以来一直是计算机视觉领域的热门话题&#xff0c;并希望能够保持这种状态。…...

Unity中Shader的遮罩的实现

文章目录 前言一、遮罩效果的实现主要是使用对应的纹理实现的&#xff0c;在属性中暴露对应的遮罩纹理&#xff0c;对其进行采样后&#xff0c;最后相乘输出即可二、如果需要像和主要纹理一样流动&#xff0c;则需要使用和_Time篇一样的方法实现流动即可 前言 Unity中Shader的…...

架构师成长之路|Redis key过期清除策略

Eviction policies maxmemory 100mb 当我们设置的内存达到指定的内存量时,清除策略的配置方式决定了默认行为。Redis可以为可能导致使用更多内存的命令返回错误,也可以在每次添加新数据时清除一些旧数据以返回到指定的限制。 当达到最大内存限制时,Redis所遵循的确切行为是…...

ubuntu20.04使用privoxy进行http代理转http代理,并定制http代理头(hide-user-agent的使用方法)

#sudo apt-get update;sudo apt install -y privoxy #sudo apt remove privoxyprivoxy --version; rootfv-az1239-825:/tmp# privoxy --version Privoxy version 3.0.28 (https://www.privoxy.org/) rootfv-az1239-825:/tmp# 安装完毕后,先停止服务,修改配置文件,再启动服…...

任意文件读取

文章目录 渗透测试漏洞原理任意文件读取1. 任意文件读取概述1.1 漏洞成因1.2 漏洞危害1.3 漏洞分类1.4 任意文件读取1.4.1 文件读取1.4.2 任意文件读取1.4.3 权限问题 1.5 任意文件下载1.5.1 一般情况1.5.2 PHP实现1.5.3 任意文件下载 2. 任意文件读取攻防2.1 路径过滤2.1.1 过…...

微信小程序餐饮外卖系统设计与实现

摘 要 随着现在的“互联网”的不断发展。现在传统的餐饮业也朝着网络化的方向不断的发展。现在线上线下的方式来实现餐饮的获客渠道增加&#xff0c;可以更好地帮助餐饮企业实现更多、更广的获客需求&#xff0c;实现更好的餐饮销售。截止到2021年末&#xff0c;我国的外卖市场…...

一文速览嵌入式六大出口

嵌入式行业的前景确实十分广阔&#xff0c;并且在许多领域都发挥着重要作用。以下是一些关键点&#xff0c;说明嵌入式系统的发展潜力和前途&#xff1a; 1. 物联网&#xff08;IoT&#xff09;&#xff1a;嵌入式系统是实现智能家居、智能城市、智能工厂等物联网设备的核心。物…...

华为云云服务器评测 | 宝塔8.0镜像应用

目录 &#x1f352;写在前面 &#x1f352;产品优势 &#x1f352;购买服务器 &#x1f352;服务器配置 &#x1f352;登录宝塔页面 &#x1f990;博客主页&#xff1a;大虾好吃吗的博客 &#x1f990;专栏地址&#xff1a;闲谈专栏地址 写在前面 云耀云服务器L实例是新一代开箱…...

构建简单的Node.js HTTP服务器,发布公网远程访问的快速方法

文章目录 前言1.安装Node.js环境2.创建node.js服务3. 访问node.js 服务4.内网穿透4.1 安装配置cpolar内网穿透4.2 创建隧道映射本地端口 5.固定公网地址 前言 Node.js 是能够在服务器端运行 JavaScript 的开放源代码、跨平台运行环境。Node.js 由 OpenJS Foundation&#xff0…...

ModaHub魔搭社区:向量数据库产业的现状与技术挑战

I. 向量数据库的崛起 什么是向量数据库 在过去的一段时间里,向量数据库逐渐在数据库领域崭露头角。那么,什么是向量数据库呢?简单来说,向量数据库是一种专门设计用来处理向量数据的数据库。这些向量数据可以是物理测量、机器学习模型输出、地理空间数据等。向量数据库使用…...

pmp和软件高项哪个含金量高?

人们常将PMP和高项放在一起比较&#xff0c;因为这两种证书都适用于项目经理职位&#xff0c;它们有高达60%的知识点重合度。在决定考哪一种证书之前&#xff0c;人们常常会感到困惑。 下面看一下pmp和软考高项的差异。 发证机构不同 PMP(Project Management Professional)是…...

手把手教你用Vite构建第一个Vue3项目

写在前面 在之前的文章中写过“如何创建第一个vue项目”&#xff0c;但那篇文章写的是创建vue2的 项目。 传送门如何创建第一个vue项目 打开Vue.js官网:https://cn.vuejs.org/&#xff0c;我们会发现Vue 2 将于 2023 年 12 月 31 日停止维护 虽然Vue2的项目还不少&#xff0…...

美创科技获通信网络安全服务能力评定(应急响应一级)认证!

近日&#xff0c;中国通信企业协会公布通信网络安全服务能力评定2023年第一批获证企业名单。 美创科技获得应急响应一级资质&#xff0c;成为2023年第一批获证企业之一&#xff01; 通信网络安全服务能力评定是对通信网络安全服务单位从事通信网络安全服务综合能力的评定&#…...

计算机视觉与人工智能在医美人脸皮肤诊断方面的应用

一、人脸皮肤诊断方法 近年来&#xff0c;随着计算机技术和人工智能的不断发展&#xff0c;中医领域开始逐渐探索利用这些先进技术来辅助面诊和诊断。在皮肤望诊方面&#xff0c;也出现了一些现代研究&#xff0c;尝试通过图像分析技术和人工智能算法来客观化地获取皮肤相关的…...

RCU501 RMP201-8 KONGSBERG 分布式处理单元

RCU501 RMP201-8 KONGSBERG 分布式处理单元 AutoChief600使用直接安装在主机接线盒中的分布式处理单元。进出发动机的所有信号都在双冗余CAN线路(发动机总线)上传输。 所有不重要的传感器都可以与K-Chief 600报警和监控系统共享&#xff0c;只需要一个主机接口。这一原则大大…...

说说 MVCC 的工作原理?

分析&回答 多版本并发控制(MVCC) InnoDB的MVCC&#xff0c;是通过在每行记录后面保存两个隐藏的列来实现。这两个列&#xff0c;一个保存了行的创建时间&#xff0c;一个保存行的删除时间&#xff0c;并不是实际的时间&#xff0c;而是系统版本号。每开始一个新的事务&am…...

微信小程序请求接口返回的二维码(图片),本地工具和真机测试都能显示,上线之后不显示问题

请求后端接口返回的图片&#xff1a; 页面展示&#xff1a; 代码实现&#xff1a; :show-menu-by-longpress"true" 是长按保存图片 base64Code 是转为base64的地址 <image class"code" :src"base64Code" alt"" :show-menu-by-long…...

Python小知识 - 1. Python装饰器(decorator)

Python装饰器&#xff08;decorator&#xff09; Python装饰器是一个很有用的功能&#xff0c;它可以让我们在不修改原有代码的情况下&#xff0c;为已有的函数或类添加额外的功能。 常见的使用场景有&#xff1a; a. 函数缓存&#xff1a;对于一些计算量较大的函数&#xff0c…...

如何访问GitHub

1、手动修改hosts 1.1、查找到最新的GitHub的hosts信息 通过链接&#xff1a;https://raw.hellogithub.com/hosts 进行查找最新的GitHub的hosts信息 1.2、查找到hosts文件位置 先找到 hosts 文件的位置&#xff0c;不同操作系统&#xff0c;hosts 文件的存储位置也不同&…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

pycharm 设置环境出错

pycharm 设置环境出错 pycharm 新建项目&#xff0c;设置虚拟环境&#xff0c;出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...

6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙

Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...

在 Visual Studio Code 中使用驭码 CodeRider 提升开发效率:以冒泡排序为例

目录 前言1 插件安装与配置1.1 安装驭码 CodeRider1.2 初始配置建议 2 示例代码&#xff1a;冒泡排序3 驭码 CodeRider 功能详解3.1 功能概览3.2 代码解释功能3.3 自动注释生成3.4 逻辑修改功能3.5 单元测试自动生成3.6 代码优化建议 4 驭码的实际应用建议5 常见问题与解决建议…...

WEB3全栈开发——面试专业技能点P4数据库

一、mysql2 原生驱动及其连接机制 概念介绍 mysql2 是 Node.js 环境中广泛使用的 MySQL 客户端库&#xff0c;基于 mysql 库改进而来&#xff0c;具有更好的性能、Promise 支持、流式查询、二进制数据处理能力等。 主要特点&#xff1a; 支持 Promise / async-await&#xf…...

MeshGPT 笔记

[2311.15475] MeshGPT: Generating Triangle Meshes with Decoder-Only Transformers https://library.scholarcy.com/try 真正意义上的AI生成三维模型MESHGPT来袭&#xff01;_哔哩哔哩_bilibili GitHub - lucidrains/meshgpt-pytorch: Implementation of MeshGPT, SOTA Me…...

Linux操作系统共享Windows操作系统的文件

目录 一、共享文件 二、挂载 一、共享文件 点击虚拟机选项-设置 点击选项&#xff0c;设置文件夹共享为总是启用&#xff0c;点击添加&#xff0c;可添加需要共享的文件夹 查询是否共享成功 ls /mnt/hgfs 如果显示Download&#xff08;这是我共享的文件夹&#xff09;&…...

Netty自定义协议解析

目录 自定义协议设计 实现消息解码器 实现消息编码器 自定义消息对象 配置ChannelPipeline Netty提供了强大的编解码器抽象基类,这些基类能够帮助开发者快速实现自定义协议的解析。 自定义协议设计 在实现自定义协议解析之前,需要明确协议的具体格式。例如,一个简单的…...