-
2020-07-15 10:56:17
若已知任意两种遍历序列,是否可以唯一确定一颗二叉树?
答:只要这两种序列包含一个中序序列就可以。
为什么一个先序和一个后序序列无法确定?
答:先序 根左右
后序 左右根
若一棵树,其中一个或多个结点的左子树或右子树为空,那么此时无法判断到底是左子树为空还是右子树为空,就会出现两种情况。
例:先序和中序遍历序列来确定一棵二叉树
解法:
根据先序遍历序列第一个结点确定根结点;
根据根结点在中序遍历序列中分割出左右两个子序列
对左子树和右子树分别递归使用相同的方法继续分解。
注意:
你可以假设树中没有重复的元素。例如,给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:3
/
9 20
/
15 7来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
代码1:简洁但是比较浪费空间/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int m= preorder.size(); if(m==0)return NULL;//递归结束的条件 TreeNode* root = new TreeNode; root->val=preorder[0]; vector<int>preorder_left,preorder_right,inorder_left,inorder_right; int leftsize=0;//左子树的长度 for(int i=0;i<m;i++) { if(inorder[i]==preorder[0])break; leftsize++; } for(int i=1;i<leftsize+1;i++) preorder_left.push_back(preorder[i]); for(int i=leftsize+1;i<m;i++) preorder_right.push_back(preorder[i]); for(int i=0;i<leftsize;i++) inorder_left.push_back(inorder[i]); for(int i=leftsize+1;i<m;i++) inorder_right.push_back(inorder[i]); root->left=buildTree( preorder_left, inorder_left); root->right=buildTree( preorder_right, inorder_right); return root; //执行用时:224 ms //内存消耗:152.8 MB } };
方法二:复杂但十分快捷且无需消耗多余的空间
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int m=preorder.size(); return mybuildTree(0,m-1,0,m-1, preorder, inorder); } TreeNode* mybuildTree(int p_left,int p_right,int i_left,int i_right,vector<int>& preorder, vector<int>& inorder){ if(p_left>p_right||i_left>i_right)return NULL;// 递归结束的条件 TreeNode *root =new TreeNode(preorder[p_left]); int leftsize=0;//左子树的长度 for(int i=i_left;i<=i_right;i++) { if(inorder[i]==preorder[p_left])break; leftsize++; }//用左子树的长度去确定各个左右子树的序列长度 root->left = mybuildTree(p_left + 1,p_left+leftsize ,i_left ,i_left+leftsize ,preorder,inorder ); root->right = mybuildTree(p_left+leftsize+1,p_right,i_left+leftsize+1,i_right,preorder,inorder); return root; } }; //执行用时:68 ms //内存消耗:17.6 MB,内存节省了10倍
方法三:在中序遍历中对根节点进行定位时,一种简单的方法是直接扫描整个中序遍历的结果并找出根节点,但这样做的时间复杂度较高。我们可以考虑使用哈希映射(HashMap)来帮助我们快速地定位根节点。对于哈希映射中的每个键值对,键表示一个元素(节点的值),值表示其在中序遍历中的出现位置。在构造二叉树的过程之前,我们可以对中序遍历的列表进行一遍扫描,就可以构造出这个哈希映射。在此后构造二叉树的过程中,我们就只需要 O(1)O(1) 的时间对根节点进行定位了。
//下列代码出自leetcode力扣题解class Solution { private: unordered_map<int, int> index; public: TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) { if (preorder_left > preorder_right) { return nullptr; } // 前序遍历中的第一个节点就是根节点 int preorder_root = preorder_left; // 在中序遍历中定位根节点 int inorder_root = index[preorder[preorder_root]]; // 先把根节点建立出来 TreeNode* root = new TreeNode(preorder[preorder_root]); // 得到左子树中的节点数目 int size_left_subtree = inorder_root - inorder_left; // 递归地构造左子树,并连接到根节点 // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素 root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1); // 递归地构造右子树,并连接到根节点 // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素 root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right); return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int n = preorder.size(); // 构造哈希映射,帮助我们快速定位根节点 for (int i = 0; i < n; ++i) { index[inorder[i]] = i; } return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1); } }; //执行用时:16 ms //内存消耗:17.8 MB
更多相关内容 -
8086系统中最小模式与最大模式两种工作方式的主要区别是什么?
2021-02-06 11:15:26在最大模式系统中,总是包含两个或以上微处理器,其中一个主处理器就是8086,其他的处理器称协助处理器。 和8086配合的协处理器有两个,一个是数值运算协处理器8087,一个是输入/输出协处理器8089. 8087是一种专用于...展开全部
最小模式和最大模式的主要区别为以下几方面:
1、处理系统方面
最小模式:系统里e68a843231313335323631343130323136353331333366306533就8086(或8088)一个微处理器而已,属于单处理系统。
最大模式:系统里除了8086(或8088)一个微处理器之外,还多增加了8288总线控制器,属于多处理剂系统。
2、运用系统方面
最小模式:相对于最大模式而言,一般使用在小规模的8086(或8088)系统中。
最大模式:是相对于最小规模而言的,一般用在中等规模的或者大型的8086(或8088)系统中。
3、管脚引用方面:
最小模式:8086(或8088)系统中,该模式下M√10管脚可以直接引用。
最大模式:8086(或8088)系统中,该模式下M√10管脚不可以直接引用。
扩展资料:
8086系统中的最大模式与最小模式:
最大模式是相对最小模式而言的。最大模式用在中等规模的或者大型的8086系统中。在最大模式系统中,总是包含两个或以上微处理器,其中一个主处理器就是8086,其他的处理器称协助处理器。
和8086配合的协处理器有两个,一个是数值运算协处理器8087,一个是输入/输出协处理器8089.
8087是一种专用于数值运算的处理器,它能实现多种类型的数值操作,比如高精度的整数和浮点运算,也可以进行超越函数(如三角函数、对数函数)的计算。
CPU工作模式的选择是由硬件决定的,将8086的第33号引脚接地,则工作于最大模式,第33号引脚接高电平,则工作于最小模式。8086CPU有8条引腿(第24号~31号)在两种不同工作模式中具有不同的功能。
-
内连接的两种方式
2019-07-20 09:04:38总第156篇/张俊红在前面的文章中我们讲过两个概念,宽表和窄表,在现实业务中,数据库中很多表存储其实都是以窄表的形式来存储的,但是我们一般从数据库中获取信息的时候,都是需...总第156篇/张俊红
在前面的文章中我们讲过两个概念,宽表和窄表,在现实业务中,数据库中很多表存储其实都是以窄表的形式来存储的,但是我们一般从数据库中获取信息的时候,都是需要同时从多个表中来获取信息,也就是需要将多个窄表先进行连接,然后再进行 select。连接方式主要有四种:左连接、右连接、内连接、外连接。默认是内连接(划重点,考试会考,但是貌似很多人不知道)。
今天我们不讲别的,只讲一下关于内连接的两种实现方式。
现在有两张表 ta 和 tb,ta 存储了学生的基础信息,tb 存储了学生的课程信息,现在想要看一下每个学生具体的课程信息,就需要把 ta 和 tb 进行连接,且只看那些报了课程的同学,有的学生可能没有报名课程。
ta 表信息如下:
stuid name classid 2019001 皇湘君 C001 2019002 张运馨 C002 2019003 周雄 tb 表信息如下:
classid classname teacher C001 数据库的发展史 兴斌斌 C002 如何成为一名优秀的数据工程师 方忻忻 C003 数据分析师如何学习Sql取数 禄晨星 要想实现我们的需求,我们可以有两种实现形式:
方式一,直接来看代码:select ta.stuid as stuid ,ta.name as name ,tb.classname as classname ,tb.teacher as teacher from ta,tb where ta.classid = tb.classid
得到的结果如下:
stuid name classname teacher 2019001 皇湘君 数据库的发展史 兴斌斌 2019002 张运馨 如何成为一名优秀的数据工程师 方忻忻 方式二,直接来看代码:
select ta.stuid as stuid ,ta.name as name ,tb.classname as classname ,tb.teacher as teacher from ta inner join tb on ta.classid = tb.classid
方式一和方式得到的结果是一样的,既然结果是一样的,为啥要有两种方式来写呢?第一种书写方式是比较古老的一种写法,对于内连接现在比较常用的,也是比较推荐的写法是第二种方式。我们上面举的例子中只涉及了两个表,但在实际业务中往往不止连接两个表,这个时候用第一种方式不仅写起来会比较抓狂、别人看起来也比较乱,性能也会下降很多。而用第二种方式,可以一直 inner join,不管连接多少个表,看起来都不至于特别乱。如果你还在使用第一种写法,建议切换到第二种。
你还可以看:
-
一个负责排序的程序包,实现多种排序算法
2011-03-20 19:46:10设计一个负责排序的程序包,实现多种排序算法,至少包括插入排序、冒泡...5.至少用两种方案编程实现该程序包,并说明两个方案的优缺点 6.提交设计报告,包括:使用UML设计的类图;主要程序代码说明;方案优缺点比较。 -
C++ 多态的两种形式
2018-09-19 17:02:26C++中的多态性具体体现在编译和运行两个阶段。编译时多态是静态多态,在编译时就可以确定接口使用的形式。运行时多态是动态多态,具体引用的接口在运行时才能确定。 静态多态和动态多态的区别其实只是在什么时候将...1.多态的概念与分类
多态(Polymorphisn)是面向对象程序设计(OOP)的一个重要特征。多态字面意思为多种状态。在面向对象语言中,一个接口,多种实现即为多态。C++ 中的多态性具体体现在编译和运行两个阶段。编译时多态是静态多态,在编译时就可以确定使用的接口。运行时多态是动态多态,具体引用的接口在运行时才能确定。
静态多态和动态多态的区别其实只是在什么时候将函数实现和函数调用关联起来,是在编译时期还是运行时期,即函数地址是早绑定还是晚绑定的。静态多态是指在编译期间就可以确定函数的调用地址,并生产代码,这就是静态的,也就是说地址是早绑定。静态多态往往也被叫做静态联编。 动态多态则是指函数调用的地址不能在编译器期间确定,需要在运行时确定,属于晚绑定,动态多态往往也被叫做动态联编。2.多态的作用
为何要使用多态呢?封装可以使得代码模块化,继承可以扩展已存在的代码,他们的目的都是为了代码重用。而多态的目的则是为了接口重用。静态多态,将同一个接口进行不同的实现,根据传入不同的参数(个数或类型不同)调用不同的实现。动态多态,则不论传递过来的哪个类的对象,函数都能够通过同一个接口调用到各自对象实现的方法。
3.静态多态
静态多态往往通过函数重载和模版(泛型编程)来实现,具体可见下面代码:
#include <iostream> using namespace std; //两个函数构成重载 int add(int a, int b){ cout<<"in add_int_int()"<<endl; return a + b; } double add(double a, double b){ cout<<"in add_double_doube()"<<endl; return a + b; } //函数模板(泛型编程) template <typename T> T add(T a, T b){ cout << "in func tempalte" << endl; return a + b; } int main(){ cout<<add(1,1)<<endl; //调用int add(int a, int b) cout<<add(1.1,1.1)<<endl; //调用double add(double a, double b) cout<<add<char>('A',' ')<<endl; //调用模板函数,输出小写字母a }
程序输出结果:
in add_int_int() 2 in add_double_doube() 2.2 in func tempalte a
4.动态多态
动态多态最常见的用法就是声明基类的指针,利用该指针指向任意一个子类对象,调用相应的虚函数,可以根据指向的子类的不同而调用不同的方法。如果没有使用虚函数,即没有利用 C++ 多态性,则利用基类指针调用相应函数的时候,将总被限制在基类函数本身,而无法调用到子类中被重写的函数。因为没有多态性,函数调用的地址将是一定的,而固定的地址将始终调用同一个函数,这就无法达到“一个接口,多种实现”的目的了。
#include <iostream> using namespace std; class Base{ public: virtual void func(){ cout << "Base::fun()" << endl; } }; class Derived : public Base{ public: virtual void func(){ cout << "Derived::fun()" << endl; } }; int main(){ Base* b=new Derived; //使用基类指针指向派生类对象 b->func(); //动态绑定派生类成员函数func Base& rb=*(new Derived); //也可以使用引用指向派生类对象 rb.func(); }
程序输出结果:
Derived::fun() Derived::fun()
通过上面的例子可以看出,在使用基类指针或引用指向子类对象时,调用的函数是子类中重写的函数,这样就实现了运行时函数地址的动态绑定,即动态联编。动态多态是通过“继承+虚函数”来实现的,只有在程序运行期间(非编译期)才能判断所引用对象的实际类型,根据其实际类型调用相应的方法。具体格式就是使用 virtual 关键字修饰类的成员函数时,指明该函数为虚函数,并且派生类需要重新实现该成员函数,编译器将实现动态绑定。
参考文献
[1] 浅谈C++多态
[2] 浅谈C++多态性
[3] Effective C++ 中文第三版[M].条款41:了解隐式接口和编译期多态 -
TypeScript01:如何定义包括多种基本数据类型的数组?
2019-09-30 18:58:41在TypeScript中定义数组有两种方法: 第一种,可以在元素类型后面接上[],表示由此类型元素组成的一个数组: let list: number[] = [1, 2]; 第二种方式是使用数组泛型,Array<元素类型>: let list:... -
遗传算法与多种群算法的寻优比较.zip
2021-10-07 12:29:10通过本实验的学习,使学生了解遗传算法与多种群算法的基本知识,掌握利用这两种算法求进行比较的主要步骤。 选择相关数据,利用两种算法进行寻优,并比较两种算法的优劣。 包含实验报告和实验代码 -
Java生成随机密码(包含大写、小写、数字、特殊字符一种或多种)
2019-08-28 21:42:35某个笔试题:生成一个不少于6位的随机密码,要求含有大写字母、小写字母、数字、特殊字符中的三种。 -
NSA和SA两种组网方式均为5G
2021-01-11 21:00:515G大潮,正在加速推进。6月初工信部正式向中国电信、中国移动、中国联通、中国广电发放5G商用牌照,我国正式进入5G...目前普遍来看,5G有两种组网方式,一个是非独立组网(Non-Standalone,NSA),另一个则是独立组网(... -
YARN的两种运行模式
2018-10-02 19:58:55YARN是一种资源管理机制,可以基于这种资源管理机制运行多种计算框架,比如mapreduce和storm,任何框架与YARN的结合,都必须遵循YARN的开发模式,下图为YARN框架的基本原理。 其中,ResourceManager和... -
能将任意两个不同的事物拿来比较吗?
2021-01-14 04:05:54从有没有意义的情况考虑,分两种情况。第一种情况【不考虑意义:】物体的同种属性可以比较,包含颜色、强度、尺寸、密度、透明度、粗糙度、黏度、柔韧度、亮度、导电率、思想深度、辐射放射强度等,这些都可以比较(我... -
HTTP中GET和POST两种基本请求方法的区别
2019-07-02 11:43:36GET和POST是HTTP请求的两种基本方法,要说它们的区别,接触过WEB开发的人都能说出一二。 最直观的区别就是GET把参数包含在URL中,POST通过request body传递参数。 你可能自己写过无数个GET和POST请求,或者... -
随机变量序列的两种收敛性
2018-12-01 15:21:14随机变量序列的收敛性有多种,其中常用的是两种:依概率收敛和依分布收敛。大数定律涉及的是一种依概率收敛,中心极限定理涉及的是依分布收敛。 1、依概率收敛 为什么要研究随机变量序列的收敛性? 依... -
网络层提供的两种服务
2015-02-20 16:37:08网络层关注的是如何将分组从源端沿着网络路径送达目的端。...两种服务:网络层应该向运输层提供怎样的服务? §虚电路服务 §数据报服务 因特网:数据报服务 网络层向上只提供简单灵活的、无 -
数据库中有两种基本的锁类型
2014-08-06 21:52:55在数据库中有两种基本的锁类型:排它锁(Exclusive Locks,即X锁)和共享锁(Share Locks,即S锁)。当数据对象被加上排它锁时,其他的事务不能对它读取和修改。加了共享锁的数据对象可以被其他事务读取,但不能修改。... -
排序的两种实现(山东大学面向对象实验二)
2011-12-15 12:34:32实验二 设计一个负责排序的程序包,实现多种排序算法,至少包括插入排序...5.至少用两种方案编程实现该程序包,并说明两个方案的优缺点 6.提交设计报告,包括:使用UML设计的类图;主要程序代码说明;方案优缺点比较。 -
LTE学习笔记五:LTE两种帧结构
2018-01-06 14:19:10上、下行信息如何复用有限的无线资源,这是所有无线制式必须考虑的双工...LTE支持两种双工模式:TDD和FDD,于是LTE定义了两种帧结构:TDD帧结构和FDD帧结构。 LTE标准制定之初就充分考虑了TDD和FDD双工方式在实现中的异 -
基于OpenCV的多种条形码识别算法
2016-06-23 14:52:20该项目实现了对EAN13,Code39,Code93,Code128的条形码识别,包含了指定编码方式和不指定两种重载方式,代码结构清晰,易于新手理解,易于读者根据需求截取部分代码。旨在互相学习,高手请勿喷,谢谢。 -
VS2019配置opencv的两种方法
2020-11-11 14:20:28本文将详细讲解使用VS2019调用opencv的两种方法:一是在IDE中完成一系列配置,二是直接使用命令行编译。 一、在IDE中配置opencv 首先我们可以直接进入opencv官网下载opencv,本文不再赘述。opencv有多个版本可供下载... -
对于数据分析的方法,具体包含哪几种?
2019-03-09 16:33:05如果我们要简单的总结,数据分析的方法,具体有以下几种: 1)确定数据的准确性 这里包含了选择数据维度的合理性、数据统计的准确性。如果数据维度选择不合理、数据统计结果不精确,我们可能是无法得出正确的分析... -
SSH简介及两种远程登录的方法
2018-09-23 13:58:58SSH两种级别的远程登录 SSH的高级应用 Secure Shell(SSH) 是由 IETF(The Internet Engineering Task Force) 制定的建立在应用层基础上的安全网络协议。它是专为远程登录会话(甚至可以用Windows远程登录Linux服务器... -
JavaScript数组去重—ES6的两种方式
2017-09-27 10:31:54说明JavaScript数组去重这个问题,经常出现在面试题中,以前也写过一篇数组去重的文章,(JavaScript 数组去重的多种方法原理详解)但感觉代码还是有点不够简单,今天和大家再说两种方法,代码可是足够的少了。... -
两种常见电商sku的设计
2016-06-29 16:43:39基于属性进行扩展,支持模型连接和直连两种方式。属性可以增加和产品分类的多对多关联,这样当产品指定主分类时,便可以根据关联获得可选的sku属性了。这样设计的考虑是,由于产品个性化很强,如果通过模型关联,... -
Matlab提供的两种聚类分析方法
2018-08-10 13:54:20一种是利用 clusterdata函数对样本数据进行一次聚类,其缺点为可供用户选择的面较窄,不能更改距离的计算方法; 另一种是分步聚类: (1)找到数据集合中变量两两之间的相似性和非相似性,用pd -
关于CSV文件的描述,以下选项中错误的是: CSV文件格式是一种通用的文件格式,应用于程序之间转移表格数据|...
2021-03-04 09:52:47关于CSV文件的描述,以下选项中错误的是: CSV文件格式是一种通用的文件格式,应用于程序之间转移表格数据|CSV文件的每一行是一维数据,可以使用Python中的列表类型表示|CSV文件通过多种编码表示字符|整个CSV文件是一... -
C/C++用多种方法交换两个数a和b的值
2017-10-31 11:06:50交换两个数的值是 C中的一个经典问题,最常见的就是...这篇博文给了多种交换a和b的值的方法,包括传统的设置一个临时变量,以及应用加减法、乘除法来实现交换,并且也给出了这两种方法的缺陷,可能会出现越界,还给出了 -
java的两种多态
2010-01-26 19:33:001. Java中除了static和final方法外,其他所有的方法都是运行时绑定的。private方法都被隐式指定为final的,因此final的方法不会在运行时绑定。当在派生类中重写基类中static、final、或...包含抽象方法的类叫做抽 -
java封装数据的两种常用方式
2018-11-01 11:47:35java后台在传输数据时,会对数据进行处理封装,下面介绍一下最常用的两个方式: 1.通过bean对象进行封装 User user =new User();//User中包含三项 id ,name,sex 三项 //下边为了省事写的是静态数据代替 user.... -
Android ListView多种布局优化demo
2015-08-15 08:13:29Android ListView多种布局优化demo,使用了两种优化手段,包括convertView,ViewHolder,对应的我的博客地址是: http://blog.csdn.net/u012320459/article/details/47667869 -
高级语言程序的两种处理方式——编译和解释
2013-09-30 20:17:08这两种语言处理程序的根本区别是:在编译方式下,机器上运行的是与源程序等价的目标程序,源程序和编译程序都不再参与目标程序的执行过程;而在解释方式下,解释程序和源程序(或其某种等价表示)要参与到程序的...