Java-数据结构-二叉树-习题(三)  ̄へ ̄

文本目录:

❄️一、习题一(前序遍历非递归):

        ▶ 思路: 

        ▶ 代码: 

 ❄️二、习题二(中序遍历非递归):

         ▶ 思路: 

        ▶ 代码: 

 ❄️三、习题三(后序遍历非递归):

         ▶ 思路: 

        ▶ 代码: 

 ❄️四、习题四(选择题):

     ➷ 选则题一:

      ➷ 选则题二:

       ➷ 选则题三:

        ➷ 选则题四:

        ➷ 选则题五:

❄️五、总结:


❄️一、习题一(前序遍历非递归):

          ☞  题的链接:

                       前序遍历非递归


        ▶ 思路: 

      对于这道题呢,我们不使用递归实现,我们呢需要使用到一种结构——栈。来实现这个前序遍历的操作,因为返回的 List<Integer>  我们呢要把每次的节点的 val 值存放到 List 里面。

     我们先把根节点放入到栈中,之后遍历左子树把其都放到栈中,当 cur 为空的时候,出栈顶节点给到 top 这个临时变量中,把 top.right 给到 cur 节点,并且我们每次入栈的节点的值都要放到List 当中最后返回的是 List 这个数据结构

     我们来看看图是如何进行的:

OK,这个呢就是我们这个题的操作流程了,我们来看看代码是如何编写的: 

        ▶ 代码 

public List<Integer> preorderTraversal(TreeNode root) {List<Integer> ret = new LinkedList<>();if (root == null) {return ret;}Stack<TreeNode> stack = new Stack<>();//先把根节点入进来TreeNode cur = root;while (cur != null || !stack.isEmpty()) {while (cur != null) {//入Listret.add(cur.val);//入栈stack.push(cur);//往左子树遍历cur = cur.left;}//存储栈顶节点TreeNode top = stack.pop();//把栈顶的节点的右子树给到curcur = top.right;}return ret;}

我们的前序遍历的非递归就到这结束了,当然有前序就得有 中序和后序,我们来看看。


 ❄️二、习题二(中序遍历非递归):

          ☞  题的链接:

                      中序遍历的非递归实现


         ▶ 思路: 

    对于我们这个题呢,当我们了解了上面的代码之后呢,就是非常好写了,我们对于前序遍历是:

根   左   右。我们的中序遍历呢是: 左  根  右。所以呢这个题其实就很简单了,我们只需要把我们存储到 List 的代码,改变到我们出栈顶数据之后再存储到 List 当中,并且我们要注意我们存储到List 的 val 值应该是我们出的栈顶的数据 top 的 val 值。

     我们的代码流程和上面的题是差不多的,我们只需要改变 List 的存储顺序就可以了。

     我们来看看代码如何编写:

        ▶ 代码 

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> ret = new LinkedList<>();if (root == null) {return ret;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {while (cur != null) {stack.push(cur);cur = cur.left;}TreeNode top = stack.pop();//我们在这里进行存储到 List 中ret.add(top.val); cur = top.right;}return ret;}

 ❄️三、习题三(后序遍历非递归):

          ☞  题的链接:

                     后序遍历的非递归实现


         ▶ 思路: 

     后序遍历是:左  右  根。我们这个题的代码呢和前面两个遍历是不一样的,这个呢我们需要判断左子树和右子树都为空的情况下,才能把这个节点的值存到 List 当中所以我们不是先出栈,我们需要先 peek 一下栈顶的数据,看是否栈顶数据的右子树是否为空,为空则打印,不为空就把其右子树的节点放到 cur 中 。但是如果这样写呢,会有一些问题,我们一会在看,我们下把我们描述的代码写下:

public List<Integer> postorderTraversal(TreeNode root) {List<Integer> ret = new LinkedList<>();if (root == null) {return ret;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while(cur != null || !stack.isEmpty()) {while(cur != null) {stack.push(cur);cur = cur.left;}TreeNode top = stack.peek();if (top.right == null) {ret.add(top.val);stack.pop();}else {cur = top.right;}}return ret;}

我们来看看这个代码哪里存在问题呢? 

       所以我们需要一个临时变量,用来存储我们要出栈的节点,当我们再次循环的时候,如果 top.right == prev 这个节点,就不会进入出栈的方法中。

那么我们来看看最终的代码是什么样的:

        ▶ 代码 

public List<Integer> postorderTraversal(TreeNode root) {List<Integer> ret = new LinkedList<>();if (root == null) {return ret;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode prev = null;while (cur != null || !stack.isEmpty()) {while (cur != null) {stack.push(cur);cur = cur.left;}TreeNode top = stack.peek();if (top.right == null || top.right == prev) {ret.add(top.val);stack.pop();prev = top;} else {cur = top.right;}}return ret;}

      到这里呢,我们关于我们前中后序的非递归遍历,就到这里就结束了,我们呢之后来看看几道选择题,这几次做代码题是不是都做腻了,我们来看看新口味:选择题。 也是关于二叉树的。


 ❄️四、习题四(选择题):

     ➷ 选则题一:

某二叉树共有 399 个节点,其中 199 个度为 2 的节点,则该二叉树中叶子节点数为 ( )

A、不存在这样的二叉树

B、200

C、198

D、199

 这个选择题呢,我们使用到的公式是 : n0(度为0的节点个数) = n2(度为2的节点的个数) + 1

这样之后我们这个题就好做了,我们的 叶子节点就是度为0 的节点,所以这个题中的叶子节点数为:n0 = 199 + 1 = 200 个,所以这题我们选择 B。 


      ➷ 选则题二:

在具有 2n 个节点的完全二叉树中,叶子结点的个数为 ( )

A、n

B、n + 1

C、n - 2

D、n / 2

     这道题呢,我们呢要考虑这个总结点个数呢是奇数还是偶数的情况下,是不一样的结果的。我们的总结点是:n0 + n1 + n2 这些节点的总数。

     当我们的总结点个数为偶数的时候呢,我们的 n1 为 1 ,

     当我们的总结点的个数为奇数的时候呢,我们的 n1 是 0。

注意:这道题我们还是需要借助 n0 = n2 + 1 这个公式

我们再来看看总结点数为奇数的情况是什么样的:   

     我们再回到这道题中,我们的总结点数为 2n 是偶数,所以这里我们使用偶数的情况进行计算,

就可以得出我们的 叶子结点(n0) 是 n 个。


       ➷ 选则题三:

我们来举一个总结点数为奇数的情况是什么样的:

                                                   一个总结点为 767 个节点的完全二叉树,其 叶子节点 个数为 ( )

A、383

B、384

C、385

D、386

   我们来看看这道题是怎样做的,我们的这个题的节点数为 767 是奇数个,所以我们使用 奇数的节点个数来计算 叶子节点。

767 = n0 + n2

767 = n0 + n0 - 1

766 = 2n0

n0 = 383

 由此可知,我们这个题的 叶子节点 的个数就是 383 个。所以我们选择 A。


        ➷ 选则题四:

  接下来我们来看看对于遍历的题:

设一颗二叉树的中序遍历为:badce,后序遍历为:bdeca,则二叉树的前序遍历是什么 ( )

A、adbce

B、decab

C、debca

D、abcde

    这种题呢,我们需要记住 前中后序  遍历的顺序,用给的两个遍历呢去还原二叉树,之后再遍历我们需要的那个二叉树就可以了。 我们来看看这道题,

    我们的 后序遍历是:左  右  根所以我们的后序遍历的最后一个值就是根节点之后到中序遍历:左   根   右去寻找根节点,把左子树和右子树分割出来,再去后序遍历中寻找 右子树的根节点,再到中序中寻找,循环执行这个操作,直至后序没有节点,这个呢就是我们的上个博客中的编码题,变成了我们的选择题。

     

     这个就是这个题的二叉树了,之后我们再对其进行前序遍历就可以了,最后我们的到 前序遍历为:abcde。所以这道题就选择 D。


        ➷ 选则题五:

某二叉树的后序遍历和中序遍历的序列是相同的,均为ABCDEF,则按照 层序遍历是 ( )

A、FEDCBA

B、CBAFED

C、DEFCBA

D、ABCDEF

   这道题呢,我们要知道我们的 后序遍历是: 左  右  根。中序遍历是:左  根  右。

   他们的遍历顺序是不同的,所以要是想要它们的遍历循序是一样的话,我们的右子树是没有节点的,这样呢结果就可以是一样的了,当我们的右子树为空后序遍历就是:先左再根。中序遍历就是:先左再根。就是一样的了。比如这道题的二叉树就可以得到这样的:

所以我们可以得知,我们的层序遍历在这里就是:FEDCBA 。所以这道题我们选择 A。


❄️五、总结:

          OK,我们的这个关于我们的二叉树的习题三但这里就结束了,同时到这里呢,我们的

数据结构 ——二叉树 也就结束了,之后呢我们进入到新的章节了,欲知后事如何,且听下回分说

拜拜啦~~~我们下篇博客再见。

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

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

相关文章

一款源码阅读的插件

文章目录 进度汇报功能预览添加高亮标记高亮风格设置笔记颜色设置数据概览高亮数据详情 结尾 进度汇报 之前提到最近有在开发一个源码阅读的IDEA插件&#xff0c;第一版已经开发完上传插件市场了&#xff0c;等官方审批通过就可以尝鲜了。插件名称&#xff1a;Mark source cod…

算法之搜索--最长公共子序列LCS

最长公共子序列&#xff08;longest common sequence&#xff09;:可以不连续 最长公共子串&#xff08;longest common substring&#xff09;&#xff1a;连续 demo for (int i 1;i<lena;i){for (int j 1;j<lenb;j){if(a[i-1]b[j-1]){dp[i][j]dp[i-1][j-1]1;}el…

java企业办公自动化OA

技术架构&#xff1a; sshjbpm 功能描述&#xff1a; 用户管理&#xff0c;岗位管理&#xff0c;部门管理&#xff0c;权限管理&#xff0c;网上交流&#xff0c;贴吧&#xff0c;审批流转。权限管理是树状结构人性化操作&#xff0c;也可以用作论坛。 效果图&#xff1a;

三维手势 第一人称 汽车驾驶 handpose 3D RGB 单目相机手势识别 手势检测 手势3D建模 三维建模

三维手势 第一人称 汽车驾驶 handpose 3D RGB 单目相机手势识别 手势检测 手势3D建模 三维建模 第一人称汽车安全驾驶 &#xff1a;三维手势建模 RGB 单目相机手势识检测 手势3D建模 咨询合作 DataBall 项目&#xff0c;欢迎加以下微信。 助力快速掌握数据集的信息和使用方式…

OpenAI API key not working in my React App

题意&#xff1a;OpenAI API 密钥在我的 React 应用中不起作用 问题背景&#xff1a; I am trying to create a chatbot in my react app, and Im not able to generate an LLM powered response. Ive been studying documentation and checking out tutorials but am unable …

PostgreSQL维护——解决索引膨胀和数据死行

注意&#xff1a; 本文内容于 2024-09-16 00:40:33 创建&#xff0c;可能不会在此平台上进行更新。如果您希望查看最新版本或更多相关内容&#xff0c;请访问原文地址&#xff1a;PostgreSQL维护——解决索引膨胀和数据死行。感谢您的关注与支持&#xff01; 我有一张表&#…

Android相关线程基础

线程基础 进程与线程 进程:可以被看做是程序的实体, 是系统进行资源分配和调度的基本单位. 线程:是操作系统调度的最小单元, 也叫轻量级进程 使用多线程的优点 可以减少程序的响应时间。如果某个操作很耗时, 能够避免陷入长时间的等待, 从而有着更好的交互性. 线程较之进…

《深度学习》深度学习 框架、流程解析、动态展示及推导

目录 一、深度学习 1、什么是深度学习 2、特点 3、神经网络构造 1&#xff09;单层神经元 • 推导 • 示例 2&#xff09;多层神经网络 3&#xff09;小结 4、感知器 神经网络的本质 5、多层感知器 6、动态图像示例 1&#xff09;一个神经元 相当于下列状态&…

Minio环境搭建(单机安装包、docker)(一)

前言&#xff1a; 项目中客户不愿意掏钱买oss&#xff0c;无奈只能给他免费大保健来一套。本篇文章只是记录验证可行性&#xff0c;毕竟minio太少文档了&#xff0c;参考着官网来。后面还会再出一套验证集群部署的文章。 一、资料 MinIO官网&#xff1a; MinIO | S3 Compatib…

CSP-J算法基础 树状结构与二叉树

文章目录 前言树状结构树状结构的基本概念&#xff1a;为什么需要树状结构&#xff1f;优点树状结构的示例 二叉树什么是二叉树&#xff1f;二叉树的类型什么样的树不是二叉树&#xff1f;二叉树的五种形态 完全二叉树相关概念完全二叉树的定义&#xff1a; 相关概念1. **高度&…

使用iperf3测试局域网服务器之间带宽

文章目录 一、下载安装1、windows2、centos 二、使用0、参数详解1、centos 一、下载安装 1、windows https://iperf.fr/iperf-download.php 拉到最下面选最新版&#xff1a; 2、centos yum install iperf3二、使用 0、参数详解 服务器或客户端&#xff1a; -p, --port #…

初识网络原理

网络的发展史 电报时代&#xff08;19世纪中叶&#xff09;&#xff1a;电报是最早的远程通信方式之一&#xff0c;它通过电线传输编码信息&#xff0c;极大地缩短了信息传递的时间电话的发明&#xff08;1876年&#xff09;&#xff1a;亚历山大格拉汉姆贝尔发明了电话&#…

前端单独实现 vue 动态路由

前端单独实现 vue 动态路由 Vue 动态路由权限是指在 Vue 应用程序中&#xff0c;根据用户的权限动态生成和控制路由的行为。这意味着不是所有的路由都在应用启动时就被硬编码到路由配置中&#xff0c;而是根据用户的权限信息&#xff0c;在运行时动态地决定哪些路由应该被加载…

VirtualBox Install MacOS

环境搭建 git clone https://github.com/myspaghetti/macos-virtualbox 脚本配置 修改macos-guest-virtualbox.sh部分内容为 vm_name"macOS" # name of the VirtualBox virtual machine macOS_release_name"Catalina" # install &quo…

EmguCV学习笔记 C# 11.6 图像分割

版权声明&#xff1a;本文为博主原创文章&#xff0c;转载请在显著位置标明本文出处以及作者网名&#xff0c;未经作者允许不得用于商业目的。 EmguCV是一个基于OpenCV的开源免费的跨平台计算机视觉库,它向C#和VB.NET开发者提供了OpenCV库的大部分功能。 教程VB.net版本请访问…

《微信小程序实战(2) · 组件封装》

&#x1f4e2; 大家好&#xff0c;我是 【战神刘玉栋】&#xff0c;有10多年的研发经验&#xff0c;致力于前后端技术栈的知识沉淀和传播。 &#x1f497; &#x1f33b; CSDN入驻不久&#xff0c;希望大家多多支持&#xff0c;后续会继续提升文章质量&#xff0c;绝不滥竽充数…

天津大学推出“AI学长”

B站&#xff1a;啥都会一点的研究生公众号&#xff1a;啥都会一点的研究生 AI圈又发生了啥新鲜事&#xff1f; 天津大学推出“AI 学长”海棠棠&#xff0c;全天候解答新生疑问 天津大学未来技术学院研发了名为“海棠棠”的新生智能体&#xff0c;它能够24小时不间断地为新生…

Oracle 19c异常恢复—ORA-01209/ORA-65088---惜分飞

由于raid卡bug故障,导致文件系统异常,从而使得数据库无法正常启动,客户找到我之前已经让多人分析,均未恢复成功,查看alert日志,发现他们恢复的时候尝试resetlogs库,然后报ORA-600 kcbzib_kcrsds_1错误 2024-09-15T17:07:32.55321508:00 alter database open resetlogs 2024-09-…

【iOS】push和present的区别

【iOS】push和present的区别 文章目录 【iOS】push和present的区别前言pushpop presentdismiss简单小demo来展示dismiss和presentdismiss多级 push和present的区别区别相同点 前言 在iOS开发中&#xff0c;我们经常性的会用到界面的一个切换的问题&#xff0c;这里我们需要理清…

C++11新增特性:lambda表达式、function包装器、bind绑定

一、lambda表达式 1&#xff09;、为啥需要引入lambda&#xff1f; 在c98中&#xff0c;我们使用sort对一段自定义类型进行排序的时候&#xff0c;每次都需要传一个仿函数&#xff0c;即手写一个完整的类。甚至有时需要同时实现排升序和降序&#xff0c;就需要各自手写一个类&…