Collection与数据结构 二叉树(三):二叉树精选OJ例题(下)

1.二叉树的分层遍历

OJ链接
在这里插入图片描述
上面这道题是分层式的层序遍历,每一层有哪些结点都很明确,我们先想一想普通的层序遍历怎么做

/*** 层序遍历* @param root*/public void levelOrder1(Node root){Queue<Node> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()){Node cur = queue.poll();System.out.println(cur.value);if (cur.left != null){queue.offer(cur.left);}if (cur.right != null){queue.offer(cur.right);}}}

这里我们通过申请队列的方式来实现层序遍历.按照从左到右的方式依次把结点依次存入队列中.

整体思路:

  1. 首先把根节点放入队列中,之后让根结点出队列.
  2. 把根结点的左结点和右结点放入队列中.
  3. 第二层放完之后,再把根结点的左结点出队列,把它的左右结点再放入队列中.再把根结点的右结点出队列,把它的左右结点再放入队列中.
  4. 以此类推,这样便可以做到从左到右,从上到下.

下面我们来实现分层操作:

/*** 层序遍历(分层)* @param root* @return*/public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> lists = new ArrayList<>();Queue<Node> queue = new LinkedList<>();if (root == null){//root为空直接返回空列表return lists;}queue.offer(root);//把根节点放进去while (!queue.isEmpty()){//队列不为空继续给lists中添加元素int size = queue.size();//获取队列大小,就是该层元素的大小List<Integer> list = new ArrayList<>();//每一层都有一个Listwhile (size != 0){//当size--为0的时候,证明这一层添加完成Node cur = queue.poll();list.add(cur.value);//忽略警告,下面的两个条件会把cur限制住if (cur.left != null){//左子树不为空,把根的左结点放进来queue.offer(cur.left);}if (cur.right != null){queue.offer(cur.right);//右子树不为空,把根的右结点放进来}size--;}lists.add(list);//每一层遍历完都添加到lists中}return lists;}

技巧性:

这里使用了size这个巧妙的变量,用来记录当前队列的大小.我们每一层都会申请一个list,把当前层数中的结点全部放入该list中,当队列的size–为0 ,说明该层的结点遍历完成,把该层的list放入总的lists中.

子问题:判断一棵树是否是完全二叉树

/*** 判断一棵树是否是完全二叉树* @param root* @return*/public boolean isCompeteTree(Node root){Queue<Node> queue = new LinkedList<>();//申请队列queue.offer(root);//把根节点放入Node cur = queue.poll();//弹出根节点赋给curwhile (cur != null){queue.offer(cur.left);queue.offer(cur.right);cur = queue.poll();//这里需要注意的是,根结点的左右子树如果为null也要放入}while(!queue.isEmpty()){Node cur1 = queue.poll();if (cur1 != null){return false;//让元素出队列,如果出的过程中遇到不是空的情况,说明不是完全二叉树}}return true;}

整体思路:
我们下面只介绍与上面问题不同的地方

  1. 这道题和上面的问题有所不同的一个点就是,即使遍历到最后,cur的左右仍然为空,也要放入队列中.
  2. 在遍历完成之后出队列的时候,如果在出到不等于null的元素,即在层序遍历完成之后,队列中仍然存在元素,此时就不是完全二叉树,否者为完全二叉树.

2. 最近公共祖先

OJ链接
在这里插入图片描述

/*** 寻找公共祖先,分为root是p,q中的一个,在root同侧,在root异侧* @param root* @param p* @param q* @return*/public Node lowestCommonAncestor(Node root, Node p, Node q) {if (root == null){return null;//如果是空树返回null}if (root == p || root == q){return root;//如果p或者q中有一个是根结点,那么根结点就是公共祖先}Node leftnode = lowestCommonAncestor(root.left,p,q);//向左子树递归Node rightnode = lowestCommonAncestor(root.right,p,q);//向右子树递归if (leftnode != null && rightnode != null){return root;//如果左子树和右子树返回的都不是null,说明p,q在root两侧,root是公共祖先} else if (leftnode == null) {return rightnode;//如果左子树返回null,说明p,q同在root右侧,返回右侧先找到的结点}else {return leftnode;//同理}}

这道题分为这几种情况:

  1. p,q其中有一个是根结点,直接返回root.
  2. p,q在根结点的异侧,则在返回的时候,根结点左子树和右子树返回的都不是空,这种情况返回的就是root.
  3. p,q在根结点的同侧,根结点左子树或者右子树有其中一个返回空,那么它们的子树中又有可能是上面的1或者2中的情况,返回子树得到的返回值即可.

3. 中序前序遍历构造二叉树

OJ链接
在这里插入图片描述

/*** 中序前序遍历构造二叉树* @param preorder 前序遍历* @param inorder 中序遍历* @return*/public int preindex = 0;//注意遍历前序数组的时候,要设置为成员变量public Node buildTree(int[] preorder, int[] inorder) {return buildTreeChild(preorder,inorder,0,inorder.length-1);}private Node buildTreeChild (int[] preorder, int[] inorder, int ibegin ,int iend){if (ibegin > iend){return null;//遍历中序数组,遍历到头大于尾的时候,返回null}int inorderindex = findIndex(inorder,preorder[preindex],ibegin,iend);//在中序数组中寻找前序遍历到的字符串//找到的即为树的根结点preindex ++;//向后遍历前序数组Node node = new Node(inorder[inorderindex]);//创建结点Node leftnode = buildTreeChild(preorder,inorder,ibegin,inorderindex-1);node.left = leftnode;//向中序数组的左遍历,构建左子树Node rightnode = buildTreeChild(preorder,inorder,inorderindex+1,iend);node.right = rightnode;//向中序数组的右遍历,构建右子树return node;}private int findIndex (int[] inorder, int order,int ibegin, int iend){for (int i = ibegin; i <= iend; i++) {if (inorder[i] == order){return i;}}return -1;}

整体思路:

  1. 由于前序遍历可以决定根节点,所以我们要拿着前序遍历数组的元素在中序遍历数组的的元素中寻找对应元素,即根结点,并创建根结点.并找到中序遍历数组中对应的下标位置.(inorderindex)
  2. 之后创建左子树,向下递归,在0~inorderindex-1的范围之中创建左子树.
  3. 之后创建右子树,向下递归,在inorderindex+1~inorder.length-1的范围之中创建右子树.

注意:
遍历前序数组的preindex应该设置为成员变量,否者在每次递归的时候preindex不会向下走,又会返回原来的值.

4. 后序遍历和中序遍历构建二叉树

OJ链接
在这里插入图片描述

/*** 后序遍历和中序遍历构建二叉树* @param inorder* @param postorder* @return*/public int postindex = 0;public Node buildTree2(int[] inorder, int[] postorder) {postindex = postorder.length-1;return buildTreeChild2(inorder,postorder,0,inorder.length-1);}private Node buildTreeChild2(int[] inoder, int[] postorder,int ibegin,int iend){if (ibegin > iend){return null;}int inorderindex = findIndex2(inoder,postorder[postindex],ibegin,iend);Node node = new Node(inoder[inorderindex]);postindex--;Node rightnode = buildTreeChild2(inoder,postorder,inorderindex+1,iend);node.right = rightnode;Node leftnode = buildTreeChild2(inoder,postorder,ibegin,inorderindex-1);node.left = leftnode;//由于后序遍历数组的顺序为左右根,所以在从后向前遍历的时候,遍历完根之后是右//所以要先构建右子树,再构建左子树return node;}private int findIndex2(int[] inorder,int order,int ibegin,int iend){for (int i = ibegin; i <= iend; i++) {if (order == inorder[i]){return i;}}return -1;}

注意:

  1. 与前序遍历不同的是,这里遍历后序数组的变量为postindex,大小为postorder.length-1,在途中让postindex- -.
  2. 子树先构建右子树,再构建左子树,因为:由于后序遍历数组的顺序为左右根,所以在从后向前遍历的时候,遍历完根之后是右,所以要先构建右子树,再构建左子树.

5. 根据二叉树创建字符串(采用前序遍历)

OJ链接
在这里插入图片描述

/*** 根据二叉树创建字符串,采用前序遍历* @param root* @return*/StringBuilder stringBuilder = new StringBuilder();//创建stringbuilderpublic String tree2str(Node root) {if (root == null){return null;//空树返回null}stringBuilder.append(root.value);//添加根结点的值if (root.left != null){stringBuilder.append("(");tree2str(root.left);//添加左结点stringBuilder.append(")");}else {if (root.right != null){stringBuilder.append("()");//如果左结点为空,看右结点是否为空,如果不为空,添加()}}if (root.right != null){//添加右结点stringBuilder.append("(");tree2str(root.right);stringBuilder.append(")");}return stringBuilder.toString();}

整体思路:

  1. 创建StringBuilder对象.
  2. 先把根结点放入,之后向左子树遍历.
  3. 如果左结点不为空,键入括号,并键入左结点的值.
  4. 如果左结点为空,又分为两种情况:右结点为空,直接什么都不做,右结点不为空,键入空的括号.
  5. 向右子树遍历.
  6. 构建好StringBilder对象之后,使用toString方法转为String.

6. 二叉树的非递归前序遍历

OJ链接
在这里插入图片描述

/*** 二叉树的非递归前序遍历 ->借助栈* @param root* @return*/public List<Integer> preorderTraversal(Node root) {List<Integer> list = new ArrayList<>();//创建顺序表if (root == null){return list;//如果为空树,返回空顺序表}Stack<Node> stack = new Stack<>();//创建栈,使用栈代替递归Node cur = root;//cur指向根while (cur != null || !stack.isEmpty()) {while (cur != null) {//cur遍历到空stack.push(cur);//把根结点放入栈中,用入栈的方式代替递归中递的过程list.add(cur.value);//并放入顺序表,完成了前序遍历的第一步,根cur = cur.left;//向左遍历,完成了前序遍历的第二部,左//循环回去又是下一个根,有到了前序遍历的第一步}Node top = stack.pop();//开始返回,用出栈的方式代替递归的归的过程cur = top.right;//cur遍历到右结点,循环回去完成了前序遍历的第三部,右}return list;}

整体思路:

  1. 该题需要借助栈来代替递归的过程.
  2. 先使得cur指向root.
  3. 把cur放入栈中,并放入list中,之后cur向左结点走,依次都把向左走的结点放入栈中.
  4. 在出栈的时候,top得到出栈元素,拿着出栈元素找到top结点的右结点,之后依次循环3,4两步.

注意:

  1. 在top拿到出栈元素之后,如果没有外层循环,该结点右结点就无法执行思路中的第三步.
  2. 出栈的时候,栈有可能为空,所以要添加!stack.isEmpty().

7. 二叉树的非递归中序遍历

在这里插入图片描述

/*** 二叉树的非递归中序遍历 ->借助栈* @param root* @return*/public List<Integer> inorderTraversal(Node root) {List<Integer> list = new ArrayList<>();//创建顺序表if (root == null){return list;//如果为空树,返回空顺序表}Stack<Node> stack = new Stack<>();//创建栈,使用栈代替递归Node cur = root;//cur指向根while (cur != null || !stack.isEmpty()) {while (cur != null) {//cur遍历到空stack.push(cur);//把根结点放入栈中,用入栈的方式代替递归中递的过程cur = cur.left;//向左遍历//循环回去,让左结点入栈}Node top = stack.pop();//开始返回,用出栈的方式代替递归的归的过程list.add(top.value);//为顺序表添加结点cur = top.right;//cur遍历到右结点//循环回去,可能遍历到最后,top的右节点是空,但是栈不为空,走下来就可以把根节点放入list中}return list;}

与前序的不同点:

  1. 在左结点入栈的时候,不入list
  2. 在最后出栈的时候先把左结点放入list中,最后cur的右为null,但是栈不为空,所以可以进入下一层循环,就可以得到原来cur上一层的根节点.

8. 二叉树的非递归后序遍历

OJ链接
在这里插入图片描述

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

注意:
在走到最后的时候,会出现死循环,所以我们要使用prev来记录最近存入list的结点,以避免死循环

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

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

相关文章

Geeker-Admin:基于Vue3.4、TypeScript、Vite5、Pinia和Element-Plus的开源后台管理框架

Geeker-Admin&#xff1a;基于Vue3.4、TypeScript、Vite5、Pinia和Element-Plus的开源后台管理框架 一、引言 随着技术的不断发展&#xff0c;前端开发领域也在不断演变。为了满足现代应用程序的需求&#xff0c;开发人员需要使用最新、最强大的工具和技术。Geeker-Admin正是…

Ubuntu 22上安装Anaconda3。下载、安装、验证详细教程

在Ubuntu 22上安装Anaconda3&#xff0c;你可以遵循以下步骤&#xff1a; 更新系统存储库&#xff1a; 打开终端并运行以下命令来更新系统存储库&#xff1a; sudo apt update安装curl包&#xff1a; 下载Anaconda安装脚本通常需要使用curl工具。如果系统中没有安装curl&#x…

流媒体的安全谁来保障

流媒体的安全谁来保障 说起媒体&#xff0c;我们马上就会想到报纸新闻、广播、电视。 其实所谓的流媒体同我们通常所指的媒体是不一样的&#xff0c; 它只是一个技术名词。流媒体到底是什么&#xff1f;能给我们的生活带来什么&#xff1f;跟小德一起来看看。 流媒体是什么&a…

OSI七层网络模型 —— 筑梦之路

在信息技术领域&#xff0c;OSI七层模型是一个经典的网络通信框架&#xff0c;它将网络通信分为七个层次&#xff0c;每一层都有其独特的功能和作用。为了帮助记忆这七个层次&#xff0c;有一个巧妙的方法&#xff1a;将每个层次的英文单词首字母组合起来&#xff0c;形成了一句…

REINFORCE及进阶算法讲解笔记

REINFORCE 总结 估计VALUE-methods没有在理论上证明收敛&#xff0c;而policy-methods不需要估计value function。 本算法总结了过去的算法&#xff0c;将过去算法作为特例看待&#xff0c;证明了即使是结合函数估计和实际采样的value梯度都可以无偏估计&#xff0c;证明了某种…

PC-lint 学习之配置方法

1. 下载PC-lint 9.0后&#xff0c;点击pclint9setup.exe进行安装&#xff08;我只安装了C/C语言&#xff0c;其他语言可安装时选择&#xff09; 2.安装完成后&#xff0c;打开keil5&#xff0c;选择配置 3. 配置选项 &#xff08;1&#xff09;Lint Executable&#xff1a;在第…

知识图谱与人工智能:携手共进

知识图谱与人工智能&#xff1a;携手共进 一、引言&#xff1a;知识图谱与人工智能的融合 在这个数据驱动的时代&#xff0c;知识图谱与人工智能&#xff08;AI&#xff09;之间的融合不仅是技术发展的必然趋势&#xff0c;也是推动各行各业创新的关键。知识图谱&#xff0c;作…

docker 上达梦导入dump文件报错:本地编码:PG GBK,导入女件编码:PGGB18030

解决方案&#xff1a; 第一步进入达梦数据容器内部 docker exec -it fc316f88caff /bin/bash 第二步&#xff1a;在容器中 /opt/dmdbms/bin目录下 执行命令 cd /opt/dmdbms/bin./dimp USERIDSYSDBA/SYSDBA001 FILE/opt/dmdbms/ZFJG_LJ20240407.dmp SCHEMASZFJG_LJUSERIDSYSD…

Guava里一些比较常用的工具

随着java版本的更新提供了越来越多的语法和工具来简化日常开发&#xff0c;但是我们一般用的比较早的版本所以体验不到。这时就用到了guava这个包。guava提供了很多方便的工具方法&#xff0c;solar框架就依赖了guava的16.0.1版本&#xff0c;这里稍微介绍下。 一、集合工具类…

深度学习图像处理基础工具——opencv 实战2 文档扫描OCR

输入一个文档&#xff0c;怎么进行文档扫描&#xff0c;输出扫描后的图片呢&#xff1f; 今天学习了 opencv实战项目 文档扫描OCR 问题重构&#xff1a;输入图像 是一个含有文档的图像——> 目标是将其转化为 规则的扫描图片 那么怎么实现呢&#xff1f; 问题分解&#…

CSS快速入门

目录 一、CSS介绍 1、什么是CSS&#xff1f; ​编辑2、基本语法规范 3、引入方式 4、规范 二、CSS选择器 1、标签选择器 2、类&#xff08;class&#xff09;选择器 3、id选择器 4、通配符选择器 5、复合选择器 三、常用CSS 1、color 2、font-size 3、border 4…

对于缓冲区的理解

目录 1、回车和换行 2、缓冲区 1、回车和换行 回车换行\n其实是两个动作 回车是回到开始位置 换行是换到下一行 &#xff08;老式键盘&#xff09; 而老式键盘是从打字机来的 \r只是回车&#xff0c;回到开始位置 2、缓冲区 fflush&#xff08;stdout&#xff09;#强制刷新缓…

手写商城项目学习/复习到的知识

1.在windowr创建项目可以选择自定义/vue2/vue3,但尝试在vscode不能选择. 2.vant vant是组件库,可导入结构等.vant2用于vue2,vant3,vant\4用于vue3 vant2的使用 官网: Vant 2 - 轻量、可靠的移动端组件库 (gitee.io) 全部导入:将vant所有的组件放到了所有组件内component使…

FMix: Enhancing Mixed Sample Data Augmentation 论文阅读

1 Abstract 近年来&#xff0c;混合样本数据增强&#xff08;Mixed Sample Data Augmentation&#xff0c;MSDA&#xff09;受到了越来越多的关注&#xff0c;出现了许多成功的变体&#xff0c;例如MixUp和CutMix。通过研究VAE在原始数据和增强数据上学习到的函数之间的互信息…

【设计模式学习】单例模式和工厂模式

꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好&#xff0c;我是xiaoxie.希望你看完之后,有不足之处请多多谅解&#xff0c;让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转…

算法——倍增

. - 力扣&#xff08;LeetCode&#xff09; 给你一棵树&#xff0c;树上有 n 个节点&#xff0c;按从 0 到 n-1 编号。树以父节点数组的形式给出&#xff0c;其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。 树节点的第 k 个祖先节点是从该节点到根节点路径…

步骤大全:网站建设3个基本流程详解

一.领取一个免费域名和SSL证书&#xff0c;和CDN 1.打开网站链接&#xff1a;https://www.rainyun.com/z22_ 2.在网站主页上&#xff0c;您会看到一个"登陆/注册"的选项。 3.点击"登陆/注册"&#xff0c;然后选择"微信登录"选项。 4.使用您的…

恢复MySQL!是我的条件反射,PXB开源的力量...

&#x1f4e2;&#x1f4e2;&#x1f4e2;&#x1f4e3;&#x1f4e3;&#x1f4e3; 哈喽&#xff01;大家好&#xff0c;我是【IT邦德】&#xff0c;江湖人称jeames007&#xff0c;10余年DBA及大数据工作经验 一位上进心十足的【大数据领域博主】&#xff01;&#x1f61c;&am…

二极管分类及用途

二极管分类及用途 通用开关二极管 特点&#xff1a;电流小&#xff0c;工作频率高 选型依据&#xff1a;正向电流、正向压降、功耗&#xff0c;反向最大电压&#xff0c;反向恢复时间&#xff0c;封装等 类型&#xff1a;BAS316 ; IN4148WS 应用电路: 说明&#xff1a;应用…

并发编程之ThreadLocal使用及原理

ThreadLocal主要是为了解决线程安全性问题的 非线程安全举例 public class ThreadLocalDemo {// 非线程安全的private static final SimpleDateFormat sdf new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");public static Date parse(String strDate) throws ParseExc…