算法——层序遍历和中序遍历构造二叉树

晴问 通过中序遍历判断左右子树,接着从层序遍历中,把左子树的层序遍历和右子树的层序遍历提取出来

#include <bits/stdc++.h>using namespace std;vector<int> in, cc;struct treeNode {int data;treeNode *left;treeNode *right;treeNode(int data) : data(data), left(nullptr), right(nullptr) {}
};treeNode *dfs(treeNode *&root, vector<int> &level, int in_left, int in_right) {if (level.size() == 0) return nullptr;int curRootNum = level[0], rootInIndex;for (rootInIndex = in_left; rootInIndex <= in_right; ++rootInIndex) {if (in[rootInIndex] == curRootNum) break;}root = new treeNode(curRootNum);set<int> leftTree;for (int i = in_left; i < rootInIndex; ++i) {leftTree.insert(in[i]);}vector<int> level_left, level_right;for (int i = 0; i < level.size(); ++i) {if (level[i] == curRootNum) continue;if (leftTree.find(level[i]) != leftTree.end()) {level_left.push_back(level[i]);} else {level_right.push_back(level[i]);}}dfs(root->left, level_left, in_left, rootInIndex - 1);dfs(root->right, level_right, rootInIndex + 1, in_right);return root;
}vector<int> result;void preOrder(treeNode *root) {if (root == nullptr) return;result.push_back(root->data);preOrder(root->left);preOrder(root->right);
}int main() {int n;cin >> n;for (int i = 0; i < n; ++i) {int num;cin >> num;cc.push_back(num);}for (int i = 0; i < n; ++i) {int num;cin >> num;in.push_back(num);}treeNode *root;dfs(root, cc, 0, n - 1);preOrder(root);for (int i = 0; i < result.size(); ++i) {cout << result[i];if (i != result.size() - 1) cout << " ";}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/34932.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

82.HarmonyOS NEXT 性能优化指南:从理论到实践

温馨提示&#xff1a;本篇博客的详细代码已发布到 git : https://gitcode.com/nutpi/HarmonyosNext 可以下载运行哦&#xff01; HarmonyOS NEXT 性能优化指南&#xff1a;从理论到实践 文章目录 HarmonyOS NEXT 性能优化指南&#xff1a;从理论到实践1. 性能优化概述1.1 性能指…

树莓派急速安装ubuntu;映射磁盘与储存磁盘文件;ubuntu映射整个工程;保存系统工作状态

一、用途 在使用树莓派上下载ubuntu时&#xff0c;需要一张sd卡&#xff0c;当你需要给这张卡做备份的时候&#xff0c;可以是使用磁盘映射软件&#xff0c;从而达到备份的目的 同时有一些大佬发布了ubuntu的映射文件&#xff0c;可以直接使用该文件&#xff0c;然后还原他的整…

Qt 控件概述 QPushButton 与 QRadioButton

目录 QPushButton setIcon 设置图标 setShortCut 设置快捷键 setAutoRepeat : 设置是否连发 ​编辑RadioButton 槽函数 单选按钮的分组排异 QPushButton QPushButtoon继承于QAbstractButton(抽象类)&#xff1b; QAbstract中与QPushButton关联性极大的属性 ​ setIcon…

HR9110 玩具单通道直流电机驱动器

1、描述 HR9110是应用于直流电机方案的单通道H桥驱动器芯片。HR9110的H桥驱动部分采用低导通电阻的PMOS和NMOS功率管。低导通电阻保证芯片低的功率损耗&#xff0c;使得芯片安全工作更长时间。此 外HR9110拥有低待机电流、低静态工作电流。这些性能使能HR9110易用于玩具方案。…

Mac 使用 Crossover 加载 Windows Steam 游戏库,实现 Windows/Mac 共享移动硬盘

Mac 使用 Crossover 加载 Windows Steam 游戏库&#xff0c;实现 Windows/Mac 共享移动硬盘 1. 在Crossover上安装Steam2. Steam容器加载移动硬盘3. 配置Steam库 前言&#xff1a;本文介绍了如何在Crossover上安装Steam并加载外接移动硬盘&#xff0c;实现在Window上下载的游戏…

ubuntu 24 安装 python3.x 教程

目录 注意事项 一、安装不同 Python 版本 1. 安装依赖 2. 下载 Python 源码 3. 解压并编译安装 二、管理多个 Python 版本 1. 查看已安装的 Python 版本 2. 配置环境变量 3. 使用 update-alternatives​ 管理 Python 版本 三、使用虚拟环境为项目指定特定 Python 版本…

沐数科技数据开发岗笔试题2025

描述性统计 标准差 答案: A 解析: 标准差 衡量数据集中数值变化或离散程度的一种度量。它反映了数据集中的各个数值与数据集的平均值&#xff08;均值&#xff09;之间的偏离程度。标准差越大&#xff0c;表明数据的分布越分散&#xff1b;标准差越小&#xff0c;表明数据…

ChatGPT-4

第一章&#xff1a;ChatGPT-4的技术背景与核心架构 1.1 生成式AI的发展脉络 生成式人工智能&#xff08;Generative AI&#xff09;的演进历程可追溯至20世纪50年代的早期自然语言处理研究。从基于规则的ELIZA系统到统计语言模型&#xff0c;再到深度学习的革命性突破&#x…

vulkanscenegraph显示倾斜模型(5.3)-相机

前言 在Vulkan中&#xff0c;相机的概念并非由API直接提供&#xff0c;而是由应用程序实现。相机的核心功能包括视图变换和投影变换&#xff1a;视图变换将世界坐标系中的物体转换到相机坐标系&#xff0c;投影变换则将相机坐标系中的物体转换到投影空间。在VSG&#xff08;Vul…

【Pycharm】Pycharm无法复制粘贴,提示系统剪贴板不可用

我也没有用vim的插件&#xff0c;检查了本地和ubutnu上都没有。区别是我是远程到ubutnu的pycharm&#xff0c;我本地直接控制windowes的pycharm是没问题的。现象是可以从外部复制到pycharm反之则不行。 ctl c ctlv 以及右键 都不行 参考&#xff1a;Pycharm无法复制粘贴&…

MySQL 8 设置允许远程连接(Windows环境)

&#x1f31f; MySQL 8 设置允许远程连接&#xff08;Windows环境&#xff09; 在开发和部署应用时&#xff0c;经常需要从远程主机连接到MySQL数据库。默认情况下&#xff0c;MySQL仅允许本地连接&#xff0c;因此需要进行一些配置才能允许远程访问。今天&#xff0c;我将详细…

Prosys OPC UA Gateway:实现 OPC Classic 与 OPC UA 无缝连接

在工业自动化的数字化转型中&#xff0c;设备与系统之间的高效通信至关重要。然而&#xff0c;许多企业仍依赖于基于 COM/DCOM 技术的 OPC 产品&#xff0c;这给与现代化的 OPC UA 架构的集成带来了挑战。 Prosys OPC UA Gateway 正是为解决这一问题而生&#xff0c;它作为一款…

欢乐力扣:基本计算器

文章目录 1、题目描述2、思路代码括号 1、题目描述 基本计算器。  给你一个字符串表达式 s &#xff0c;请你实现一个基本计算器来计算并返回它的值。  注意:不允许使用任何将字符串作为数学表达式计算的内置函数&#xff0c;比如 eval() 。 2、思路 本人也不太会&#xff0c…

SVN学习笔记

svn:版本控制软件 解决&#xff1a;1.协作开发 2.远程开发 3.版本回退 服务端软件&#xff1a; VisualSVN http://www.visualsvn.com 客户端软件:Tortoisesvn http://tortoisesvn.net/downloads 1.checkout(检出) 第一查更新数据到本地&#xff0c; 2.update&#xf…

Mysql表的查询

一&#xff1a;创建一个新的数据库&#xff08;companydb),并查看数据库。 二&#xff1a;使用该数据库&#xff0c;并创建表worker。 mysql> use companydb;mysql> CREATE TABLE worker(-> 部门号 INT(11) NOT NULL,-> 职工号 INT(11) NOT NULL,-> 工作时间 D…

[ISP] 人眼中的颜色

相机是如何记录颜色的&#xff0c;又是如何被显示器还原的&#xff1f; 相机通过记录RGB数值然后显示器显示RGB数值来实现颜色的记录和呈现。道理是这么个道理&#xff0c;但实际上各厂家生产的相机对光的响应各不相同&#xff0c;并且不同厂家显示器对三原色的显示也天差地别&…

Cursor插件市场打不开解决

问题现象&#xff1a; cursor搜索插件的时候提示错误&#xff0c;无法搜索安装插件 error while fetching extensions.failed to fetch 问题原因 cursor默认安装使用的并不是vs code的插件市场&#xff0c;国内网络有时候打不开 解决 修改插件市场地址并重启cursor 打开cur…

R 语言科研绘图 --- 密度图-汇总

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…

安卓屏保调试

安卓屏保调试 - Wesley’s Blog 先看一下在设置点击屏保预览后的调用链&#xff08;Android 14&#xff09; #mermaid-svg-YQ66ef7zSvNutCCW {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-YQ66ef7zSvNutCCW .erro…

考研系列-408真题计算机网络篇(18-23)

写在前面 此文章是本人在备考过程中408真题计算机网络部分&#xff08;2018年-2023年&#xff09;的易错题及相应的知识点整理&#xff0c;后期复习也常常用到&#xff0c;对于知识提炼归纳理解起到了很大的作用&#xff0c;分享出来希望帮助到大家~ # 2018 1.停止-等待协议的…