【算法与数据结构】106、LeetCode从中序与后序遍历序列构造二叉树
文章目录
- 一、题目
- 二、解法
- 三、完整代码
所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。
一、题目

二、解法
思路分析:首先我们要知道后序遍历数组的最后一个元素必然是根节点,然后根据根节点在中序遍历数组中的位置进行划分,得到根节点的左右子树遍历数组,以此递归。当然这里有一个前提,遍历数组的元素不得重复,否则构造的二叉树不唯一。因此我们根据根节点的值找到中序遍历数组中的根节点索引,以此划分出左右区间,然后进行递归。
程序如下:
class Solution {
public:TreeNode* traversal(const vector<int>& inorder, int inorderBegin, int inorderEnd, const vector<int>& postorder, int postorderBegin, int postorderEnd) { // 1、判断是否为空数组,直接返回if (inorderBegin == inorderEnd || postorderBegin == postorderEnd) return NULL;// 2、后序遍历数组最后一个元素,就是当前的中间节点int rootValue = postorder[postorderEnd - 1]; TreeNode* root = new TreeNode(rootValue);// 3、叶子节点,后序数组只剩下一个元素,树构造完毕,返回if (postorderBegin - postorderEnd == 1) return root;// 4、找切割点int delimiterIndex;for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {if (inorder[delimiterIndex] == rootValue) break; // 这里注意二叉树遍历数组的值不能重复,否则二叉树不唯一,这里默认是唯一二叉树,值不重复。}// 5、切割中序数组,得到 中序左数组和中序右数组int leftinorderBegin = inorderBegin;int leftinorderEnd = delimiterIndex;int rightinorderBegin = delimiterIndex + 1;int rightinorderEnd = inorder.size();// 6、切割后序数组,得到 后序左数组和后序右数组int leftpostorderBegin = postorderBegin;int leftpostorderEnd = postorderBegin + delimiterIndex - inorderBegin;// 右后序区间,左闭右开[rightPostorderBegin, rightPostorderEnd)int rightPostorderBegin = postorderBegin + (delimiterIndex - inorderBegin);int rightPostorderEnd = postorderEnd - 1; // 排除最后一个元素,已经作为节点了// 7、递归root->left = traversal(inorder, leftinorderBegin, leftinorderEnd, postorder, leftpostorderBegin, leftpostorderEnd);root->right = traversal(inorder, rightinorderBegin, rightinorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());}
};
三、完整代码
# include <iostream>
# include <vector>
# include <queue>
# include <string>
# include <algorithm>
# include <stack>
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:TreeNode* traversal(const vector<int>& inorder, int inorderBegin, int inorderEnd, const vector<int>& postorder, int postorderBegin, int postorderEnd) { // 1、判断是否为空数组,直接返回if (inorderBegin == inorderEnd || postorderBegin == postorderEnd) return NULL;// 2、后序遍历数组最后一个元素,就是当前的中间节点int rootValue = postorder[postorderEnd - 1]; TreeNode* root = new TreeNode(rootValue);// 3、叶子节点,后序数组只剩下一个元素,树构造完毕,返回if (postorderBegin - postorderEnd == 1) return root;// 4、找切割点int delimiterIndex;for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {if (inorder[delimiterIndex] == rootValue) break; // 这里注意二叉树遍历数组的值不能重复,否则二叉树不唯一,这里默认是唯一二叉树,值不重复。}// 5、切割中序数组,得到 中序左数组和中序右数组int leftinorderBegin = inorderBegin;int leftinorderEnd = delimiterIndex;int rightinorderBegin = delimiterIndex + 1;int rightinorderEnd = inorder.size();// 6、切割后序数组,得到 后序左数组和后序右数组int leftpostorderBegin = postorderBegin;int leftpostorderEnd = postorderBegin + delimiterIndex - inorderBegin;// 右后序区间,左闭右开[rightPostorderBegin, rightPostorderEnd)int rightPostorderBegin = postorderBegin + (delimiterIndex - inorderBegin);int rightPostorderEnd = postorderEnd - 1; // 排除最后一个元素,已经作为节点了// 7、递归root->left = traversal(inorder, leftinorderBegin, leftinorderEnd, postorder, leftpostorderBegin, leftpostorderEnd);root->right = traversal(inorder, rightinorderBegin, rightinorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());}
};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;}
}// 层序遍历
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;
}int main()
{//vector<int> inorder = {9, 3, 15, 20, 7};//vector<int> postorder = { 9, 15, 7, 20, 3 };vector<int> inorder = { 1, 2, 3};vector<int> postorder = { 3, 2, 1};Solution s;TreeNode* root = s.buildTree(inorder, postorder);vector<vector<int>> tree = levelOrder(root);my_print2<vector<vector<int>>, vector<int>>(tree, "目标树:");system("pause");return 0;
}
end
相关文章:
【算法与数据结构】106、LeetCode从中序与后序遍历序列构造二叉树
文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析:首先我们要知道后序遍历数组的最后一个元素必然是根节点,然后根据根节点在中序遍历数组中的…...
kali 安装cpolar内网穿透实现 ssh 远程连接
文章目录 1. 启动kali ssh 服务2. kali 安装cpolar 内网穿透3. 配置kali ssh公网地址4. 远程连接5. 固定连接SSH公网地址6. SSH固定地址连接测试 简单几步通过cpolar 内网穿透软件实现ssh 远程连接kali! 1. 启动kali ssh 服务 默认新安装的kali系统会关闭ssh 连接服务,我们通…...
算法训练 第一周
一、合并两个有序数组 本题给出了两个整数数组nums1和nums2,这两个数组均是非递减排列,要求我们将这两个数组合并成一个非递减排列的数组。题目中还要求我们把合并完的数组存储在nums1中,并且为了存储两个数组中全部的数据,nums1中…...
软件评测师之码制
目录 一、机器数二、码制三、数的表示范围 一、机器数 机器数就是一个数在计算机中的二进制表示,计算机中机器数的最高位是符号位,正数符号位为0,负数符号位为1,机器数包含原码、反码和补码三种表示形式。 二、码制 表现形式数…...
ubuntu18安装cmake27的方法
背景是ubuntu18默认的cmake是3.10 $ apt search cmake Sorting... Done Full Text Search... Done bear/bionic,bionic 2.3.11-1 allgenerate compilation database for Clang toolingcatkin/bionic,bionic 0.7.8-1 allLow-level build system macros and infrastructure for …...
通讯编程006——NodeJS OPC UA Client开发简单教程
本文介绍如何在NodeJS环境下开发OPC UA Client,通过本文可以对OPC UA的基本概念有所了解,掌握OPC UA的本质。相关软件请登录网信智汇(wangxinzhihui.com)。 开发步骤如下: 1)首先需要安装nodejs,要求版本至少是12。 …...
「高等数学」雅可比矩阵和黑塞矩阵的异同
「高等数学」雅可比矩阵和黑塞矩阵的异同 雅可比矩阵,Jacobi matrix 或者 Jacobian,是向量值函数( f : R n → R m f:\mathbb{R}^n \to \mathbb{R}^m f:Rn→Rm)的一阶偏导数按行排列所得的矩阵。 黑塞矩阵,又叫海森矩…...
继承(个人学习笔记黑马学习)
1、基本语法 #include <iostream> using namespace std; #include <string>//普通实现页面//Java页面 //class Java { //public: // void header() { // cout << "首页、公开课、登录、注册...(公共头部)" << endl; // } // void footer() …...
ToBeWritten之ATTCK 测评方案
也许每个人出生的时候都以为这世界都是为他一个人而存在的,当他发现自己错的时候,他便开始长大 少走了弯路,也就错过了风景,无论如何,感谢经历 转移发布平台通知:将不再在CSDN博客发布新文章,敬…...
JSONUtil详解
JSONUtil是一个通用的JSON工具类,用于在Java中操作JSON数据。虽然之前提到的示例中没有直接提及JSONUtil,但可以解释一下可能存在的一些常见JSON操作方法,这些方法通常可以在不同的JSON工具类中找到。 JSONUtil中的一些常见方法包括…...
ArcGIS Maps SDK for JS(一):概述与使用
文章目录 1 概述2 如何使用ArcGIS Maps SDK for JavaScript2.1 AMD 模块与 ES 模块2.2 AMD 模块和 ES 模块比较 3 几种安装方式3.1 通过 ArcGIS CDN 获取 AMD 模块3.2 通过 NPM 运行 ES 模块3.3 通过 CDN 获取 ES 模块3.4 本地构建 ES3.5 本地构建 AMD 3 VSCode下载与安装2.1 下…...
【STM32】FSMC接口的复用和非复用
问题背景 在阅读《零死角玩转STM32—F103指南者》,以及《STM32F10x-中文参考手册》关于FSMC一章节的时候,对于在控制NOR/SRAM的时候使用到的引脚,在提到NOR器件的时候提到了地址复用和非复用接口,一时间没明白是什么东西。 结论 非复用模式…...
操作系统强化认识之Shell编程学习与总结
目录 1.Shell的概述 2.Shell脚本入门 3.变量 3.1.系统预定义变量 3.2.自定义变量 3.3.特殊变量 4.运算符 5.条件判断 6.流程控制 6.1.if判断 6.2.case语句 6.3.for循环 6.4.while循环 7.read读取控制台输入 8.函数 8.1.系统函数 8.2.自定义函数 9.正则表示式入…...
怎么用conda下载清华源的pytorch(自带cuda的版本)
1,添加镜像源 conda config --add channels https://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/main conda config --add channels https://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/free conda config --add channels https://mirrors.tuna.tsinghua.edu.cn…...
【ES6】CommonJS模块和ES6模块
在JavaScript中,模块是一种将功能代码组织成逻辑单元的方式,以便在其他项目中重复使用。有两种主要的模块系统:CommonJS和ES6。 1、CommonJS 在CommonJS中,我们使用require来引入模块,使用module.exports来导出模块。…...
两个线程同步执行:解决乱箭穿心(STL/Windows/Linux)
C自学精简教程 目录(必读) C并发编程入门 目录 多线程同步 线程之间同步是指线程等待其他线程执行完某个动作之后再执行(本文情况)。 线程同步还可以是像十字路口的红绿灯一样,只允许一个方向的车同行,其他方向的车等待。 本…...
Ubuntu18.04更改镜像源(网易,阿里,清华,中科大,浙大)
一,备份原来的源(选做) sudo cp /etc/apt/sources.list /etc/apt/sources_init.list 二,更换源 sudo gedit /etc/apt/sources.list 删除原来内容改为新的镜像源 1,清华源 deb https://mirrors.tuna.tsinghua.edu…...
字节码和机器码的区别
字节码和机器码是计算机程序在不同阶段的表示形式,它们的主要区别如下: 抽象级别不同:字节码是一种中间表示形式,位于源代码和机器码之间。它是一种与特定平台无关的低级表示形式,通常由编译器将源代码转换而来。而机器…...
go学习part21 Redis和Go(2)
1.三方库安装 309_尚硅谷_Go连接到Redis_哔哩哔哩_bilibili 借鉴: Golang 安装 Redis_go fiber 安装redis_柒柒伍贰玖。的博客-CSDN博客 三方redis库已经迁移到以下网址,go get github.com/gomodule/redigo/redis gomodule/redigo: Go client for Red…...
从0到1学会Git(第二部分):Git的本地操作和管理
写在前面:本文介绍了在本地仓库进行文件的处理以及本地的合并等操作。 前置知识:文件可以处在三个区域,分别为工作区,暂存区和本地仓库,我们此文的目标即是将文件存储在本地仓库中。我们可以将文件的区域理解为,cpu中,…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
全志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…...
Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...
PHP 8.5 即将发布:管道操作符、强力调试
前不久,PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5!作为 PHP 语言的又一次重要迭代,PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是,借助强大的本地开发环境 ServBay&am…...
深入理解Optional:处理空指针异常
1. 使用Optional处理可能为空的集合 在Java开发中,集合判空是一个常见但容易出错的场景。传统方式虽然可行,但存在一些潜在问题: // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...
