【算法与数据结构】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 文件的存储位置也不同&…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...

C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

Maven 概述、安装、配置、仓库、私服详解
目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...