二叉树题目:从前序与后序遍历序列构造二叉树

文章目录

  • 题目
    • 标题和出处
    • 难度
    • 题目描述
      • 要求
      • 示例
      • 数据范围
  • 前言
  • 解法一
    • 思路和算法
    • 代码
    • 复杂度分析
  • 解法二
    • 思路和算法
    • 代码
    • 复杂度分析

题目

标题和出处

标题:从前序与后序遍历序列构造二叉树

出处:889. 从前序与后序遍历序列构造二叉树

难度

7 级

题目描述

要求

给定两个整数数组 preorder \texttt{preorder} preorder postorder \texttt{postorder} postorder,其中 preorder \texttt{preorder} preorder 是一个具有无重复值的二叉树的前序遍历, postorder \texttt{postorder} postorder 是同一个树的后序遍历,请构造并返回二叉树。

如果存在多个答案,返回其中任何一个。

示例

示例 1:

示例 1

输入: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1] \texttt{preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]} preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出: [1,2,3,4,5,6,7] \texttt{[1,2,3,4,5,6,7]} [1,2,3,4,5,6,7]

示例 2:

输入: preorder = [1], postorder = [1] \texttt{preorder = [1], postorder = [1]} preorder = [1], postorder = [1]
输出: [1] \texttt{[1]} [1]

数据范围

  • 1 ≤ preorder.length ≤ 30 \texttt{1} \le \texttt{preorder.length} \le \texttt{30} 1preorder.length30
  • 1 ≤ preorder[i] ≤ preorder.length \texttt{1} \le \texttt{preorder[i]} \le \texttt{preorder.length} 1preorder[i]preorder.length
  • preorder \texttt{preorder} preorder 中所有值都不同
  • postorder.length = preorder.length \texttt{postorder.length} = \texttt{preorder.length} postorder.length=preorder.length
  • 1 ≤ postorder[i] ≤ postorder.length \texttt{1} \le \texttt{postorder[i]} \le \texttt{postorder.length} 1postorder[i]postorder.length
  • postorder \texttt{postorder} postorder 中所有值都不同
  • 保证 preorder \texttt{preorder} preorder postorder \texttt{postorder} postorder 是同一个二叉树的前序遍历和后序遍历

前言

当二叉树中的每个结点值各不相同时,给定二叉树的前序遍历与中序遍历,或者给定二叉树的中序遍历与后序遍历,都可以唯一地构造出二叉树。但是给定二叉树的前序遍历与后序遍历,则可能有多种符合要求的二叉树。

由于答案可能不唯一,因此在构造二叉树时需要做特殊处理,使得答案为可能的答案之一。在确保得到正确答案的前提下,将答案限定在一种可能。

解法一

思路和算法

由于二叉树中的每个结点值各不相同,因此可以根据结点值唯一地确定结点。

二叉树的前序遍历的方法为:依次遍历根结点、左子树和右子树,对于左子树和右子树使用同样的方法遍历。

二叉树的后序遍历的方法为:依次遍历左子树、右子树和根结点,对于左子树和右子树使用同样的方法遍历。

前序遍历序列的第一个元素值与后序遍历序列的最后一个元素值都是根结点值。如果左子树和右子树都不为空,则前序遍历序列的第二个元素值为左子结点值,后序遍历序列的倒数第二个元素值为右子结点值,由于后序遍历序列中每个子树的根结点总是最后被访问的,因此只要在后序遍历序列中定位到左子结点值的下标,即可得到左子树中的结点数和右子树中的结点数。对于左子树和右子树,也可以在给定的前序遍历序列和后序遍历序列中分别得到对应的子序列,根据子序列构造相应的子树。

如果前序遍历序列的第二个元素值与后序遍历序列的倒数第二个元素值相同,则只有一个子树不为空,左子树非空和右子树非空都是可能的情况。为了将答案限定在一种可能,当只有一个子树不为空时,规定左子树不为空,则左子树中的结点数为二叉树中的结点数减 1 1 1,右子树中的结点数为 0 0 0。对于左子树,使用同样的方法构造。

上述构造二叉树的过程是一个递归分治的过程。将二叉树分成根结点、左子树和右子树三部分,首先构造左子树和右子树,然后构造原始二叉树,构造左子树和右子树是原始问题的子问题。

分治的终止条件是子序列为空,此时构造的子树为空。当子序列不为空时,首先得到根结点值以及左子树和右子树对应的子序列,然后递归地构造左子树和右子树。

实现方面有两点需要注意。

  1. 在后序遍历序列中定位左子结点值的下标时,简单的做法是遍历整个序列寻找左子结点值,该做法的时间复杂度较高。可以使用哈希表存储每个结点值在后序遍历序列中的下标,即可在 O ( 1 ) O(1) O(1) 的时间内定位到任意结点值在后序遍历序列中的下标。

  2. 对于左子树和右子树的构造需要使用子序列,此处的子序列实质为下标连续的子数组。为了降低时间复杂度和空间复杂度,使用开始下标和子数组长度确定子数组,则不用新建数组和复制数组元素,而且可以复用哈希表存储的每个结点值在后序遍历序列中的下标信息。

代码

class Solution {Map<Integer, Integer> postorderIndices = new HashMap<Integer, Integer>();int[] preorder;int[] postorder;public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {this.preorder = preorder;this.postorder = postorder;int length = preorder.length;for (int i = 0; i < length; i++) {postorderIndices.put(postorder[i], i);}return constructFromPrePost(0, 0, length);}public TreeNode constructFromPrePost(int preorderStart, int postorderStart, int nodesCount) {if (nodesCount == 0) {return null;}int rootVal = preorder[preorderStart];TreeNode root = new TreeNode(rootVal);if (nodesCount == 1) {return root;}int leftChildVal = preorder[preorderStart + 1];int postorderLeftChildIndex = postorderIndices.get(leftChildVal);int leftNodesCount = postorderLeftChildIndex - postorderStart + 1;int rightNodesCount = nodesCount - 1 - leftNodesCount;root.left = constructFromPrePost(preorderStart + 1, postorderStart, leftNodesCount);root.right = constructFromPrePost(preorderStart + 1 + leftNodesCount, postorderLeftChildIndex + 1, rightNodesCount);return root;}
}

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是数组 preorder \textit{preorder} preorder postorder \textit{postorder} postorder 的长度,即二叉树的结点数。将后序遍历序列中的每个结点值与下标的对应关系存入哈希表需要 O ( n ) O(n) O(n) 的时间,构造二叉树也需要 O ( n ) O(n) O(n) 的时间。

  • 空间复杂度: O ( n ) O(n) O(n),其中 n n n 是数组 preorder \textit{preorder} preorder postorder \textit{postorder} postorder 的长度,即二叉树的结点数。空间复杂度主要是递归调用的栈空间以及哈希表空间,因此空间复杂度是 O ( n ) O(n) O(n)

解法二

思路和算法

使用迭代的方法构造二叉树,需要充分利用二叉树遍历的性质,考虑遍历序列中相邻结点的关系。

对于前序遍历序列中的两个相邻的值 x x x y y y,其对应结点的关系一定是以下两种情况之一:

  1. 结点 y y y 是结点 x x x 的左子结点,或者结点 x x x 没有左子结点且结点 y y y 是结点 x x x 的右子结点;

  2. 结点 x x x 是叶结点,结点 y y y 是结点 x x x 的某个祖先结点的右子结点。

对于第 1 种情况,在后序遍历序列中, y y y x x x 前面。对于第 2 种情况,在后序遍历序列中, x x x y y y 前面。

判断前序遍历序列中的两个相邻的值属于哪一种情况,需要借助后序遍历序列。由于后序遍历访问根结点在访问左右子树之后,因此可以比较前序遍历序列的上一个结点值和后序遍历序列的当前结点值,判断属于哪一种情况:

  • 如果前序遍历序列的上一个结点值和后序遍历序列的当前结点值不同,则前序遍历序列的上一个结点不是叶结点,属于第 1 种情况;

  • 如果前序遍历序列的上一个结点值和后序遍历序列的当前结点值相同,则前序遍历序列的上一个结点是叶结点,属于第 2 种情况。

注意在第 1 种情况下,后序遍历序列的结点值顺序恰好和前序遍历序列的结点值顺序相反,可以使用栈实现反转序列。

具体做法是,遍历前序遍历序列,对于每个值分别创建结点,将每个结点作为栈顶结点的左子结点,并将每个结点入栈,直到栈顶结点值等于后序遍历序列的当前结点值。然后遍历后序遍历序列并依次将栈内的结点出栈,直到栈顶结点值和后序遍历序列的当前结点值不同,此时前序遍历序列的当前值对应的结点为栈顶结点的右子结点,将当前结点入栈。然后对前序遍历序列和后序遍历序列的其余值继续执行上述操作,直到遍历结束时,二叉树构造完毕。

以下用示例 1 说明构造二叉树的过程。已知二叉树的前序遍历序列是 [ 1 , 2 , 4 , 5 , 3 , 6 , 7 ] [1, 2, 4, 5, 3, 6, 7] [1,2,4,5,3,6,7],后序遍历序列是 [ 4 , 5 , 2 , 6 , 7 , 3 , 1 ] [4, 5, 2, 6, 7, 3, 1] [4,5,2,6,7,3,1]

初始时,后序遍历序列的下标是 0 0 0。以下将后序遍历序列的下标处的值称为后序遍历序列的当前结点值。

  1. 将前序遍历序列的下标 0 0 0 的元素 1 1 1 作为根结点值创建根结点,并将根结点入栈。

  2. 当遍历到前序遍历序列的 2 2 2 时,上一个结点值和后序遍历序列的当前结点值不同,因此创建结点 2 2 2,作为结点 1 1 1 的左子结点,并将结点 2 2 2 入栈。

  3. 当遍历到前序遍历序列的 4 4 4 时,上一个结点值和后序遍历序列的当前结点值不同,因此创建结点 4 4 4,作为结点 2 2 2 的左子结点,并将结点 4 4 4 入栈。

  4. 当遍历到前序遍历序列的 5 5 5 时,上一个结点值是 4 4 4,和后序遍历序列的当前结点值相同,因此遍历后序遍历序列并将栈内的结点 4 4 4 出栈,此时后序遍历的下标移动到 1 1 1。创建结点 5 5 5,将结点 5 5 5 作为结点 2 2 2 的右子结点,并将结点 5 5 5 入栈。

  5. 当遍历到前序遍历序列的 3 3 3 时,上一个结点值是 5 5 5,和后序遍历序列的当前结点值相同,因此遍历后序遍历序列并将栈内的结点 5 5 5 2 2 2 出栈,此时后序遍历的下标移动到 3 3 3。创建结点 3 3 3,将结点 3 3 3 作为结点 1 1 1 的右子结点,并将结点 3 3 3 入栈。

  6. 当遍历到前序遍历序列的 6 6 6 时,上一个结点值和后序遍历序列的当前结点值不同,因此创建结点 6 6 6,作为结点 3 3 3 的左子结点,并将结点 6 6 6 入栈。

  7. 当遍历到前序遍历序列的 7 7 7 时,上一个结点值是 6 6 6,和后序遍历序列的当前结点值相同,因此遍历后序遍历序列并将栈内的结点 6 6 6 出栈,此时后序遍历的下标移动到 4 4 4。创建结点 7 7 7,将结点 7 7 7 作为结点 3 3 3 的右子结点,并将结点 7 7 7 入栈。

此时遍历结束,二叉树构造完毕。

代码

class Solution {public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {int length = preorder.length;TreeNode root = new TreeNode(preorder[0]);Deque<TreeNode> stack = new ArrayDeque<TreeNode>();stack.push(root);int postorderIndex = 0;for (int i = 1; i < length; i++) {TreeNode prev = stack.peek();TreeNode curr = new TreeNode(preorder[i]);if (prev.val != postorder[postorderIndex]) {prev.left = curr;stack.push(curr);} else {while (stack.peek().val == postorder[postorderIndex]) {stack.pop();postorderIndex++;}prev = stack.peek();prev.right = curr;stack.push(curr);}}return root;}
}

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是数组 preorder \textit{preorder} preorder postorder \textit{postorder} postorder 的长度,即二叉树的结点数。前序遍历序列和后序遍历序列各需要遍历一次,构造二叉树需要 O ( n ) O(n) O(n) 的时间。

  • 空间复杂度: O ( n ) O(n) O(n),其中 n n n 是数组 preorder \textit{preorder} preorder postorder \textit{postorder} postorder 的长度,即二叉树的结点数。空间复杂度主要是栈空间,取决于二叉树的高度,最坏情况下二叉树的高度是 O ( n ) O(n) O(n)

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

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

相关文章

互联网上门洗衣洗鞋工厂系统搭建;

随着移动互联网的普及&#xff0c;人们越来越依赖手机应用程序来解决生活中的各种问题。通过手机预约服务、购买商品、获取信息已经成为一种生活习惯。因此&#xff0c;开发一款上门洗鞋小程序&#xff0c;可以满足消费者对于方便、快捷、专业的洗鞋服务的需求&#xff0c;同时…

模拟瑞幸的购物车

是根据渡一大师课来写的&#xff0c;如有什么地方存在问题&#xff0c;还请大家在评论区指出来。ど⁰̷̴͈꒨⁰̷̴͈う♡&#xff5e; index.html <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta http…

【银行测试】银行项目,信用卡业务测试+常问面试(三)

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 银行测试-信用卡业…

2023年全国职业院校技能大赛软件测试赛题—单元测试卷⑧

单元测试 一、任务要求 题目1&#xff1a;根据下列流程图编写程序实现相应处理&#xff0c;执行j10*x-y返回文字“j1&#xff1a;”和计算值&#xff0c;执行j(x-y)*(10⁵%7)返回文字“j2&#xff1a;”和计算值&#xff0c;执行jy*log(x10)返回文字“j3&#xff1a;”和计算值…

帆软后台(外观配置-主题)文件上传漏洞

漏洞利用 帆软上传主题获取shell&#xff08;管理系统-外观配置&#xff09; 添加主题上传的压缩包中放入shell.jsp马 &#xff08;没有添加主题功能直接构造数据包&#xff09; POST /WebReport/ReportServer?opfr_attach&cmdah_upload&filenametest.zip&widt…

【数据结构】排序之归并排序与计数排序

个人主页 &#xff1a; zxctsclrjjjcph 文章封面来自&#xff1a;艺术家–贤海林 如有转载请先通知 目录 1. 前言2. 归并排序2.1 递归实现2.1.1 分析2.1.2 代码实现 2.2 非递归实现2.2.1 分析2.2.2 代码实现 3. 计数排序3.1 分析3.2 代码实现 4. 附代码4.1 Sort.h4.2 Sort.c4.3…

基于ssm的企业文档管理系统+vue论文

摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本企业文档管理系统就是在这样的大环境下诞生&#xff0c;其可以帮助管理者在短时间内处理完毕庞大的数据信息…

Mac上使用phpstudy+vscode配置PHP开发环境

使用的工具&#xff1a; 1、系统版本 2、vs code code 3、phpstudy_pro 一、下载vs code code以及必要的插件 1、vs code下载 点击vs code官网下载 选择对应的版本&#xff0c;一般电脑会自动识别对应的版本&#xff0c;点击下载&#xff0c;然后傻瓜式安装&#xff01; 2…

可狱可囚的爬虫系列课程 11:Requests中的SSL

一、SSL 证书 SSL 证书是数字证书的一种&#xff0c;类似于驾驶证、护照、营业执照等的电子副本。SSL 证书也称为 SSL 服务器证书&#xff0c;因为它是配置在服务器上。 SSL 证书是由受信任的数字证书颁发机构 CA 在验证服务器身份后颁发的&#xff0c;其具有服务器身份验证和…

大白菜U盘安装系统-戴尔电脑

1. 把U盘插入电脑&#xff0c;启动盘去大白菜官网找&#xff0c;镜像可以去微软官网下&#xff0c;想要专业版的网上找资源。 2. 重启电脑&#xff0c;等出现log之后狂按F12&#xff0c;进入BOSS模式。 3. 选择UEFI...也就是下面白色的&#xff0c;按下回车。 4. 选第一个 5.…

基于Python实现地标景点识别

目录 前言简介地标景点识别的背景 地标景点识别的原理卷积神经网络&#xff08;CNN&#xff09;的基本原理地标景点识别的工作流程 使用Python实现地标景点识别的步骤数据收集数据预处理构建卷积神经网络模型模型训练 参考文献 前言 简介 地标景点识别是一种基于计算机视觉技术…

SpringBoot+SSM项目实战 苍穹外卖(11) Apache ECharts

继续上一节的内容&#xff0c;本节学习Apache ECharts&#xff0c;实现营业额统计、用户统计、订单统计和销量排名Top10功能。 数据统计效果图&#xff1a; 目录 Apache ECharts入门案例 营业额统计用户统计订单统计销量排名Top10 Apache ECharts Apache ECharts 是一款基于 …

家居行业如何制定小红书策略,品牌营销须知

凭借出色的品牌传播力&#xff0c;平台一直以来都备受关注。那么作为运营&#xff0c;进入小红书后&#xff0c;该如何利用好各方特性和优势&#xff0c;进行传播呢?今天我们就和大家一起分享下家居行业如何制定小红书策略&#xff0c;品牌营销须知&#xff01; 一、小红书平台…

可应用于电脑主板等产品上的精密基准电路WL431 输出电压可设定 响应速度快

WL431为三端可调节精密基准源。通过两个外接电阻&#xff0c;输出电压可在Vref约2.5 V )到36V连续调节。该电路输出阻抗小(0.2Q)。 开启特性好&#xff0c;在许多应用场合&#xff0c;它能较好地替换齐纳极管。 主要特点&#xff1a;● 温度系数 50pmC ● 在…

自学Python笔记总结(更新中……)

自学Python笔记总结 网址数据类型类型查看类型&#xff0c;使用type内置类标识符 输出输入语句format函数的语法及用法数据类型的转换运算符算数运算符赋值运算符的特殊场景拆包 比较运算符逻辑运算符 与 短路位运算符运算符优先级 程序流程控制分支语句pass 占位 循环语句 whi…

[DM8] 达梦8配置兼容Oracle

查看版本信息 select *&#xff0c;id_code from v$version; 查询解释&#xff1a; DM Database Server 64 V8 1-1-190-21.03.12-136419-ENT 64 版本位数标识&#xff0c;64表示为64位版本&#xff0c;无64则表示为32位版本 V8 大版本号&#xff0c;目前主要是V7、V8 1-1-190…

行为型设计模式——状态模式

状态模式 状态模式是比较简单的设计模式&#xff0c;它的主要作用是减少代码中大量的 if-else 或者 switch-case 等逻辑判断&#xff08;俗称屎山&#xff09;。它将每个状态定义为一个类&#xff0c;而每个状态类有自己对应的方法&#xff0c;因此当需要根据状态执行逻辑代码…

【Web】什么是 XSS 攻击,如何避免?

&#x1f34e;个人博客&#xff1a;个人主页 &#x1f3c6;个人专栏&#xff1a;Web ⛳️ 功不唐捐&#xff0c;玉汝于成 目录 前言 正文 常见方法&#xff1a; 结语 我的其他博客 前言 在当今数字化时代&#xff0c;网络安全成为信息技术领域中的一项至关重要的任务。X…

【hcie-cloud】【20】容器详解【容器介绍,容器工作机制、容器常用命令说明】【上】

文章目录 前言容器是什么虚拟化技术的四个特点容器也是一种虚拟化技术容器是怎么实现虚拟化的&#xff1f;容器对比虚拟机有哪些优势&#xff1f;容器对比虚拟机有哪些不足&#xff1f;容器不仅是一种虚拟化技术&#xff0c;更重要的是一种应用打包机制容器提供的是PaaS服务常见…