算法宝典2——Java版本(此系列持续更新,这篇文章目前3道)(有题目的跳转链接)(此份宝典包含了二叉树的算法题)

注:由于字数的限制,我打算把算法宝典做成一个系列,一篇文章就20题!!!

目录

一、二叉树的算法题(目前3道)

1. 平衡二叉树(力扣)

2.  对称二叉树(力扣)

3. 二叉树的层序遍历(力扣)


一、二叉树的算法题(目前3道)

1. 平衡二叉树(力扣)

题目跳转链接icon-default.png?t=N7T8https://leetcode.cn/problems/balanced-binary-tree/

题目:给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 ,空树也是平衡二叉树。

思路:

代码:

    // 获取二叉树的高度public int maxDepth(TreeNode root){if(root == null){return 0;}int leftCount = maxDepth(root.left);int rightCount = maxDepth(root.right);return (leftCount > rightCount) ? leftCount + 1 : rightCount + 1;}//判断是否为平衡二叉树public boolean isBalanced(TreeNode root) {//如果为空树,返回nullif(root == null){return true;}//获取左右子树的高度int leftTreeHigh = maxDepth(root.left);int righTreeHigh = maxDepth(root.right);//isBalanced(root.left) && isBalanced(root.left)是判断左右子树是不是也满足平衡二叉树的定义return Math.abs(leftTreeHigh - righTreeHigh) < 2&& isBalanced(root.left) && isBalanced(root.right);}

如果是按照上述代码的思路来写,此算法的时间复杂度就是O(n^2)!!!这是在是太大了!

什么原因造成的呢?

答:我们在求3结点的高度时,其实就把9结点的高度求出来了,但是递归到9结点的时候,又求了一次,导致重复求树的高度,有n个结点,每个结点就要求n次高度,也就是n*n!!!

所以我们可以把代码改一下:

    public int maxDepth2(TreeNode root) {//空树,证明没有子树,他的高度就是0if(root == null){return 0;}int leftH = maxDepth2(root.left);//只要左子树的高度返回是-1,表示左子树不满足平衡二叉树的定义if(leftH < 0)return -1;int rightH = maxDepth2(root.right);//只要右子树的高度返回是-1,表示左子树不满足平衡二叉树的定义if (rightH < 0)return -1;if(Math.abs(leftH - rightH) <= 1){return Math.max(leftH,rightH) + 1;//满足定义,返回高度最高的子树,并+1}else{return -1;//不满足定义,返回-1}}public boolean isBalanced2(TreeNode root) {return maxDepth2(root) >= 0;}

运行结果:

2.  对称二叉树(力扣)

题目跳转链接icon-default.png?t=N7T8https://leetcode.cn/problems/symmetric-tree/

题目:给你一个二叉树的根节点 root , 检查它是否轴对称。

思路:

和这道判断两个二叉树是不是一样的题目类似:算法宝典1——Java版本(此系列持续更新,这篇文章有20道)(有题目的跳转链接)(此份宝典包含了链表、栈、队列、二叉树的算法题)_木子斤欠木同的博客-CSDN博客

让左子树的左结点和右子树的右子树相比较,然后递归下去,然后就可以判断是不是对称二叉树!!!

代码:

    //判断对称树public boolean isSymmetricChild(TreeNode leftChild, TreeNode rightChild) {//这是路径的判断if (leftChild != null && rightChild == null || leftChild == null && rightChild != null) {return false;}if (leftChild == null && rightChild == null) {return true;}//这是值的判断if (leftChild.val != rightChild.val) {return false;}return isSymmetricChild(leftChild.left, rightChild.right)&& isSymmetricChild(leftChild.right, rightChild.left);}public boolean isSymmetric(TreeNode root) {if (root == null) {return true;}return isSymmetricChild(root.left,root.right);}

运行结果:

3. 二叉树的层序遍历(力扣)

题目跳转链接icon-default.png?t=N7T8https://leetcode.cn/problems/binary-tree-level-order-traversal/

题目:给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。

思路:

代码:

    //不带链表的形式public void levelOrder1(TreeNode root){if(root == null){return;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){TreeNode poll = queue.poll();System.out.println(poll.val+ " ");if(poll.left != null){queue.offer(poll.left);}if(poll.left != null){queue.offer(poll.right);}}}//带链表的形式public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> List = new ArrayList<>();if(root == null){return List;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){//第一层循环表示树什么时候遍历完int size = queue.size();List<Integer> list = new ArrayList<>();while(size != 0){//第二层循环表示当前层次的元素数量TreeNode cur = queue.poll();size--;list.add(cur.val);//将元素保存到列表if(cur.left != null){queue.offer(cur.left);}if(cur.right != null){queue.offer(cur.right);}}List.add(list);}return List;}

运行结果:

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

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

相关文章

MySQL最新版8.1.0安装配置教程

目录 目录 前言 安装流程图 1&#xff0c;MySQL数据库是什么? 2&#xff0c;下载zip压缩包 3&#xff0c;解压到要安装的目录 4,添加环境变量 4.1,找到环境变量 4.2,进行环境变量的添加 5.新建mysql 配置文件 6、安装mysql服务 7、初始化数据文件 8、启动mysql …

Java面向对象编程

下列关于线性链表的叙述中&#xff0c;正确的是&#xff08; &#xff09; A. 各数据结点的存储空间可以不连续&#xff0c;但它们的存储顺序与逻辑顺序必须一致 B. 各数据结点的存储顺序与逻辑顺序可以不一致&#xff0c;但它们的存储空间必须连续 C. 进行插入与删除时&#x…

gitlab操作

1. 配置ssh 点击访问 2. 创建新分支与切换新分支 git branch 新分支名 // 创建 git checkout 新分支名 // 切换到新分支3. 查看当前分支 git branch*所指的就是当前所在分支 4. 本地删除文件后与远程git同步 git add -A git commit -m "del" git push

如何根据性能需求进行场景设计?

场景设计一 探索 测试环境 客户端: win10 这里可以用linux,但没用,因为想直观查看结果。 被测环境:linux X86 4核CPU16G内存 被测接口:登录接口,没有做数据驱动。 在测试执行前,先使用influxSQL把influxdb的数据清理一下,以防影响结果查看。 有这么一个需求,要求系…

cs224w_colab3_2023 And cs224w_colab4_2023学习笔记

class GNNStack(torch.nn.Module):def __init__(self, input_dim, hidden_dim, output_dim, args, embFalse):super(GNNStack, self).__init__() #这里的继承表示参见 https://blog.csdn.net/wanzew/article/details/106993425 # 继承时运行继承类别的函数 总之 __mro__的目的…

银河麒麟操作系统安装人大金仓数据库--九五小庞

一、环境要求 硬件&#xff1a;内存512M以上&#xff0c;磁盘空间10G以上软件&#xff1a;主流Linux操作系统&#xff0c;本机使用kylin-v10安装包准备&#xff1a;官网下载数据库文件镜像以及授权文件 https://www.kingbase.com.cn/rjcxxz/index.htm 二、配置内核参数 vim /e…

flink-1.14.4启动报错setPreferCheckpointForRecovery(Z)v

从flink1.12升级到flink1.14&#xff0c;修改了pom.xml的flink-version&#xff0c;打包的时候发现报错&#xff1a; // 当有较新的 Savepoint 时&#xff0c;作业也会从 Checkpoint 处恢复env.getCheckpointConfig().setPreferCheckpointForRecovery(true); 于是屏蔽了这段配置…

C++中的导入include,头文件,extern,main函数入口及相关编译流程

结论&#xff1a; 1&#xff1a;#include就是复制粘贴 2&#xff1a;C编译的时候&#xff0c;在链接之前&#xff0c;各个文件之间实际上没有联系&#xff0c;只有到了链接的阶段&#xff0c;系统才会到各个cpp文件中去找需要的文件&#xff1b; 一&#xff1a;include的作用…

MCU软核 3. Xilinx Artix7上运行cortex-m3软核

0. 环境 - win10 vivado 2018.3 keil mdk - jlink - XC7A35TV12 1. 下载资料 https://keilpack.azureedge.net/pack/Keil.V2M-MPS2_DSx_BSP.1.1.0.pack https://gitee.com/whik/cortex_m3_on_xc7a100t 2. vivado 2018 Create Project -> Next -> -> Project n…

timer trigger function

创建&#xff08;使用vscode&#xff09; 选择Timer trigger 命名 设置多久触发一次&#xff08;该语句是5分钟一次&#xff09; 创建完成 在下面直接编辑想要运行的代码。

Redis-渐进式遍历scan的使用

目录 1、为什么使用渐进式遍历&#xff1f; 2、scan的使用 3、渐进式遍历的缺点 4、补充知识点&#xff1a;redis中也区分database 1、为什么使用渐进式遍历&#xff1f; 前面的博客中&#xff0c;我们有提到使用keys *来获取所有的key&#xff0c;但这种办法&#xff0c;…

看好多人都在劝退学计算机,可是张雪峰又 推荐过计算机,所以计算机到底是什么样 的?

张雪峰高考四百多分&#xff0c;但是他现在就瞧不起400多分的学生。说难听点&#xff0c;六七百分的 热门专业随便报谁不会啊&#xff1f; 计算机专业全世界都是过剩的&#xff0c;今年桂林电子科技&#xff0c;以前还是华为的校招大学&#xff0c;今年 计算机2/3待业。这个世…

golang iris框架 + linux后端运行

go mod init myappgo get github.com/kataras/iris/v12latestpackage mainimport "github.com/kataras/iris/v12"func main(){app : iris.New()app.Listen(":port") }打包应用 go build main.go开启服务 #nohup ./程序名称 nohup ./main关闭后台 #ps -e…

电荷型 和 IEPE/ICP型振动传感器的比较

PE(压电式)和IEPE(集成电路压电式,PCB公司叫做ICP)传感器的对比说明,供各位参考。 1. PE/IEPE传感器的敏感元件均为压电晶体,通过压电效应感受被测物理量。 2.PE传感器:输出电荷量,也叫电荷传感器。不需要供电,两根信号线,可直接接入电荷放大器进行测量。 优点―――结…

模拟实现链式二叉树及其结构学习——【数据结构】

W...Y的主页 &#x1f60a; 代码仓库分享 &#x1f495; 之前我们实现了用顺序表完成二叉树(也就是堆)&#xff0c;顺序二叉树的实际作用就是解决堆排序以及Topk问题。 今天我们要学习的内容是链式二叉树&#xff0c;并且实现链式二叉树&#xff0c;这篇博客与递归息息相关&a…

Java-华为真题-预定酒店

需求&#xff1a; 放暑假了&#xff0c;小王决定到某旅游景点游玩&#xff0c;他在网上搜索到了各种价位的酒店&#xff08;长度为n的数组A&#xff09;&#xff0c;他的心理价位是x元&#xff0c;请帮他筛选出k个最接近x元的酒店&#xff08;n>k>0&#xff09;&#xff…

Java面向对象,全程无废话,偏实战

面向对象 定义 / 使用类 // src/Phone.java public class Phone {// 类属性String brand "苹果";int price 7999;// 类方法public void call() {System.out.println("打电话");}public void sendMessage() {System.out.println("发短信");} …

GeoJSON转STL:地形3D打印

我们通过将 GeoJSON 形状坐标提取到点云中并使用 Open3d 应用泊松重建&#xff0c;从 GeoJSON 数据重建 STL 网格。 推荐&#xff1a;用 NSDT编辑器 快速搭建可编程3D场景 我对打印 GeoJSON 山丘的第一次尝试深感不满&#xff0c;因此想出了一个三步流程&#xff0c;仅使用开源…

私域流量的优势

私域流量是指由自身品牌或个人拥有并具备完全掌控权的流量资源。它相比于传统的广告推广&#xff0c;拥有独特的优势。 首先&#xff0c;私域流量能够更加精准地定位目标用户&#xff0c;实现精准传播。不再盲目投放广告&#xff0c;而是通过建立自身社群、粉丝群&#xff0c;获…

HarmonyOS开发:那些开发中常见的问题汇总(一)

前言 本来这篇文章需要讲述静态共享包如何实现远程依赖和上传以及关于静态共享包私服的搭建&#xff0c;非常遗憾的告诉大家&#xff0c;由于组织管理申请迟迟未通过&#xff0c;和部分文档官方权限暂未开放&#xff0c;关于这方面的讲解需要延后了&#xff0c;大概需要等到202…