当前位置: 首页 > news >正文

剑指offer——JZ7 重建二叉树 解题思路与具体代码【C++】

一、题目描述与要求

重建二叉树_牛客题霸_牛客网 (nowcoder.com)

题目描述

给定节点数为 n 的二叉树的前序遍历和中序遍历结果,请重建出该二叉树并返回它的头结点。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建出如下图所示。

提示:

1.vin.length == pre.length

2.pre 和 vin 均无重复元素

3.vin出现的元素均出现在 pre里

4.只需要返回根结点,系统会自动输出整颗树做答案对比

数据范围:n≤2000,节点的值 −10000≤val≤10000

要求:空间复杂度 O(n),时间复杂度O(n)

示例

示例1:

输入:[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]

返回值:{1,2,3,4,#,5,6,#,7,#,#,8}

说明:返回根节点,系统会输出整颗二叉树对比结果,重建结果如题面图示

示例2:

输入:[1],[1]

返回值:{1}

示例3:

输入:[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]

返回值:{1,2,5,3,4,6,7}


二、解题思路

根据题目描述,给出我们一个二叉树的前序遍历与中序遍历结果来还原重建二叉树,首先我们需要了解前序遍历与中序遍历其中的规律,这样才能够通过遍历结果来还原原本的二叉树。

前序遍历——先输出根结点,然后先序遍历左子树,再先序遍历右子树。

中序遍历——中序遍历左子树,输出根结点,然后中序遍历右子树。

由此可以知道前序遍历的第一个结点就是整个二叉树的根结点,然后在中序遍历中找到这个根结点,我们就可以将遍历结果进行划分,中序遍历的前半部分就是根结点的左子树的中序遍历结果,右半部分就是根结点的右子树的中序遍历结果,同时也可以对前序遍历进行划分,前半部分为左子树的前序遍历结果,后半部分为右子树的前序遍历结果。以此来再对左子树和右子树进行相同的处理(递归),一直到遍历序列的长度为0,则结束,同时二叉树也就建立完成。

首先我们获取两个遍历结果序列的长度(用于判断是否遍历结束)。

然后利用前序遍历第一个结点来构造根结点。

然后就是在中序遍历序列中找到对应的根结点,然后将两个遍历序列进行划分成左右两部分,分别用来构造左子树和右子树。if语句末尾加上break是防止for循环继续下去浪费时间。

最后返回root即可。


三、具体代码

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param preOrder int整型vector * @param vinOrder int整型vector * @return TreeNode类*/TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {int n=preOrder.size();int m=vinOrder.size();//每个遍历都不能为0if(n==0||m==0){return nullptr;}//构造根结点TreeNode* root=new TreeNode(preOrder[0]);//前序遍历第一个结点就是根结点for(int i=0;i<vinOrder.size();i++){//在中序遍历中找到根结点,对整个结果进行划分成左子树和右子树if(preOrder[0]==vinOrder[i]){//左子树的前序遍历vector<int> leftpre(preOrder.begin()+1,preOrder.begin()+i+1);//左子树的中序遍历vector<int> leftvin(vinOrder.begin(),vinOrder.begin()+i);//构建左子树root->left=reConstructBinaryTree(leftpre, leftvin);//右子树的前序遍历vector<int> rightpre(preOrder.begin()+i+1,preOrder.end());//右子树的中序遍历vector<int> rightvin(vinOrder.begin()+i+1,vinOrder.end());//构建右子树root->right=reConstructBinaryTree(rightpre, rightvin);break;}}return root;}
};

http://www.lryc.cn/news/183490.html

相关文章:

  • 图片批量编辑器,轻松拼接多张图片,创意无限!
  • 蓝桥等考Python组别十四级008
  • 【linux进程(二)】如何创建子进程?--fork函数深度剖析
  • 数字IC前端学习笔记:数字乘法器的优化设计(华莱士树乘法器)
  • CountDownLatch 批量更改使用,
  • 910数据结构(2019年真题)
  • 推荐系统实践 笔记
  • 【JavaEE】JUC(Java.util.concurrent)常见类
  • 清除浮动的方法
  • LangChain 摘要 和问答示例
  • (32)测距仪(声纳、激光雷达、深度摄影机)
  • 教你拥有一个自己的QQ机器人!0基础超详细保姆级教学!基于NoneBot2 Windows端搭建QQ机器人
  • 智能银行卡明细筛选与统计,轻松掌握账户总花销!
  • SRT服务器SLS
  • Linux 安装 Android SDK
  • 【QT开发笔记-基础篇】| 第四章 事件QEvent | 4.4 鼠标按下、移动、释放事件
  • vue3父子通信+ref,toRef,toRefs使用实例
  • 输入电压转化为电流性 5~20mA方案
  • SpringBoot自带模板引擎Thymeleaf使用详解①
  • 推荐算法——Apriori算法原理
  • vue ant 隐藏 列
  • java基础之初始化顺序
  • FFmpeg 命令:从入门到精通 | ffmpeg filter(过滤器 / 滤镜)
  • 【C语言】23-结构体类型
  • Python小技巧:快速合并字典dict()
  • 如何使用 React 和 Docusaurus 编写的一些自定义钩子(Hook)
  • 【初识Linux】Linux环境配置、Linux的基本指令 一
  • conda常用命令参数,指定版本,依赖库文件,创建虚拟环境,删除,激活,退出,内部安装包,pip通过代理安装包
  • 【锁的区别】C++线程库和POSIX线程库锁的区别
  • 网络层·IP协议