【算法与数据结构】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题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析:【算法与数据结构】106、LeetCode从中序与后序遍历序列构造二叉树这两道题有些类似,相关代…...
您必须尝试的 4 种经典特征提取技术!
一、说明 特征提取如何实现?其手段并不是很多,有四个基本方法,作为AI工程师不能不知。因此,本篇将对四种特征提取给出系统的方法。 二、概述 图像分类长期以来一直是计算机视觉领域的热门话题,并希望能够保持这种状态。…...
Unity中Shader的遮罩的实现
文章目录 前言一、遮罩效果的实现主要是使用对应的纹理实现的,在属性中暴露对应的遮罩纹理,对其进行采样后,最后相乘输出即可二、如果需要像和主要纹理一样流动,则需要使用和_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 过…...
微信小程序餐饮外卖系统设计与实现
摘 要 随着现在的“互联网”的不断发展。现在传统的餐饮业也朝着网络化的方向不断的发展。现在线上线下的方式来实现餐饮的获客渠道增加,可以更好地帮助餐饮企业实现更多、更广的获客需求,实现更好的餐饮销售。截止到2021年末,我国的外卖市场…...
一文速览嵌入式六大出口
嵌入式行业的前景确实十分广阔,并且在许多领域都发挥着重要作用。以下是一些关键点,说明嵌入式系统的发展潜力和前途: 1. 物联网(IoT):嵌入式系统是实现智能家居、智能城市、智能工厂等物联网设备的核心。物…...
华为云云服务器评测 | 宝塔8.0镜像应用
目录 🍒写在前面 🍒产品优势 🍒购买服务器 🍒服务器配置 🍒登录宝塔页面 🦐博客主页:大虾好吃吗的博客 🦐专栏地址:闲谈专栏地址 写在前面 云耀云服务器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࿰…...
ModaHub魔搭社区:向量数据库产业的现状与技术挑战
I. 向量数据库的崛起 什么是向量数据库 在过去的一段时间里,向量数据库逐渐在数据库领域崭露头角。那么,什么是向量数据库呢?简单来说,向量数据库是一种专门设计用来处理向量数据的数据库。这些向量数据可以是物理测量、机器学习模型输出、地理空间数据等。向量数据库使用…...
pmp和软件高项哪个含金量高?
人们常将PMP和高项放在一起比较,因为这两种证书都适用于项目经理职位,它们有高达60%的知识点重合度。在决定考哪一种证书之前,人们常常会感到困惑。 下面看一下pmp和软考高项的差异。 发证机构不同 PMP(Project Management Professional)是…...
手把手教你用Vite构建第一个Vue3项目
写在前面 在之前的文章中写过“如何创建第一个vue项目”,但那篇文章写的是创建vue2的 项目。 传送门如何创建第一个vue项目 打开Vue.js官网:https://cn.vuejs.org/,我们会发现Vue 2 将于 2023 年 12 月 31 日停止维护 虽然Vue2的项目还不少࿰…...
美创科技获通信网络安全服务能力评定(应急响应一级)认证!
近日,中国通信企业协会公布通信网络安全服务能力评定2023年第一批获证企业名单。 美创科技获得应急响应一级资质,成为2023年第一批获证企业之一! 通信网络安全服务能力评定是对通信网络安全服务单位从事通信网络安全服务综合能力的评定&#…...
计算机视觉与人工智能在医美人脸皮肤诊断方面的应用
一、人脸皮肤诊断方法 近年来,随着计算机技术和人工智能的不断发展,中医领域开始逐渐探索利用这些先进技术来辅助面诊和诊断。在皮肤望诊方面,也出现了一些现代研究,尝试通过图像分析技术和人工智能算法来客观化地获取皮肤相关的…...
RCU501 RMP201-8 KONGSBERG 分布式处理单元
RCU501 RMP201-8 KONGSBERG 分布式处理单元 AutoChief600使用直接安装在主机接线盒中的分布式处理单元。进出发动机的所有信号都在双冗余CAN线路(发动机总线)上传输。 所有不重要的传感器都可以与K-Chief 600报警和监控系统共享,只需要一个主机接口。这一原则大大…...
说说 MVCC 的工作原理?
分析&回答 多版本并发控制(MVCC) InnoDB的MVCC,是通过在每行记录后面保存两个隐藏的列来实现。这两个列,一个保存了行的创建时间,一个保存行的删除时间,并不是实际的时间,而是系统版本号。每开始一个新的事务&am…...
微信小程序请求接口返回的二维码(图片),本地工具和真机测试都能显示,上线之后不显示问题
请求后端接口返回的图片: 页面展示: 代码实现: :show-menu-by-longpress"true" 是长按保存图片 base64Code 是转为base64的地址 <image class"code" :src"base64Code" alt"" :show-menu-by-long…...
Python小知识 - 1. Python装饰器(decorator)
Python装饰器(decorator) Python装饰器是一个很有用的功能,它可以让我们在不修改原有代码的情况下,为已有的函数或类添加额外的功能。 常见的使用场景有: a. 函数缓存:对于一些计算量较大的函数,…...
如何访问GitHub
1、手动修改hosts 1.1、查找到最新的GitHub的hosts信息 通过链接:https://raw.hellogithub.com/hosts 进行查找最新的GitHub的hosts信息 1.2、查找到hosts文件位置 先找到 hosts 文件的位置,不同操作系统,hosts 文件的存储位置也不同&…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...
4. TypeScript 类型推断与类型组合
一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式,自动确定它们的类型。 这一特性减少了显式类型注解的需要,在保持类型安全的同时简化了代码。通过分析上下文和初始值,TypeSc…...
MyBatis中关于缓存的理解
MyBatis缓存 MyBatis系统当中默认定义两级缓存:一级缓存、二级缓存 默认情况下,只有一级缓存开启(sqlSession级别的缓存)二级缓存需要手动开启配置,需要局域namespace级别的缓存 一级缓存(本地缓存&#…...
