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

Java二叉树面试题讲解

Java二叉树面试题讲解

  • 🚗1.检查两颗树是否相同
  • 🚕2.另一颗树的子树
  • 🚙3.二叉树最大深度
  • 🚌4.判断一颗二叉树是否是平衡二叉树
  • 🚎5.对称二叉树
  • 🚓6.获取树中结点个数
  • 🚑7.判断一个树是不是完全二叉树:

大家好,我是晓星航。今天为大家带来的是 Java二叉树面试题讲解 的讲解!😀

🚗1.检查两颗树是否相同

检查两颗树是否相同。OJ链接

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if (p == null && q == null) {return true;}if (p == null && q != null || p != null && q == null) {return false;}if (p.val != q.val) {return false;}return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}
}

思路:

1.先判断p和q是否都为空,返回true。

2.在判断p和q是否一个为空一个不为空,返回false。

3.然后再判断p的值和q的值相不相等,相等返回true,不相等返回false。

4.最后返回p和q的左节点以及右节点是否都满足位置一致且数值相同,即直接递归判断(让之后的结点重新进入我们的函数)。

🚕2.另一颗树的子树

另一颗树的子树OJ链接

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if (p == null && q != null || p != null && q == null) {return false;}if (p == null && q == null) {return true;}if (p.val != q.val) {return false;}return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}public boolean isSubtree(TreeNode root, TreeNode subRoot) {if (root == null || subRoot == null) {return false;}//根节点和subRoot是不是两颗相同的树if (isSameTree(root,subRoot)) {return true;}//subRoot是不是root的左子树if (isSubtree(root.left,subRoot)) {return true;}//subRoot是不是root的右子树if (isSubtree(root.right,subRoot)) {return true;}return false;}
}

思路:

1、先判断两棵树是不是两颗相同的子树

2、如果不是,那么分别判断subRoot是不是root的左子树或者右子树

🚙3.二叉树最大深度

二叉树最大深度OJ链接

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;}int leftHeight = maxDepth(root.left);int rightHeight = maxDepth(root.right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}   
}

思路:通过创建左树高度leftHeight与右树高度rightHeight来进行比较,并返回较大值加1给上一层函数作为结果,在最下层元素的左右结点都为null直接返回,并多次递归后,直到返回到开始的root结点的值即为我们此树的高度。

🚌4.判断一颗二叉树是否是平衡二叉树

判断一颗二叉树是否是平衡二叉树OJ链接

1、root左树的高度-右树的高度<=1
2、root的左树是平衡点,右树是平衡的

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int height(TreeNode root) {if(root == null) {return 0;}int leftHeight = height(root.left);int rightHeight = height(root.right);//return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;if (leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight - rightHeight) <= 1) {return Math.max(leftHeight,rightHeight) + 1;} else {//说明不平衡return -1;}}/***时间复杂度:O(N)*/public boolean isBalanced(TreeNode root) {if (root == null) {return true;}//int left = height(root.left);//int right = height(root.right);//return Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right);return height(root) >= 0;}
}

思路:通过平衡二叉树的性质:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1来确定我们函数的返回值从而递归。注释代码是分开实现的方法,没有注释的代码是在判断高度的时候就判断该二叉树是不是平衡二叉树如果不是则返回-1,然后加入逻辑只要leftHeightrightHeight不>=0则返回-1,提高平衡树判断效率。

注:Math.abs()是调用的Math函数中的绝对值函数,目的是返回一个正的差值。

🚎5.对称二叉树

对称二叉树OJ链接

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {if (leftTree == null && rightTree != null ||leftTree != null && rightTree == null) {return false;}if (leftTree == null && rightTree == null) {return true;}if (leftTree.val != rightTree.val) {return false;}return isSymmetricChild(leftTree.left,rightTree.right) && isSymmetricChild(leftTree.right,rightTree.left);}public boolean isSymmetric(TreeNode root) {if (root == null) {return true;}return isSymmetricChild(root.left,root.right);}
}

思路:二叉树的对称可以理解为镜像对称,即左节点的左和右节点的右 左节点的右和右节点的左是否对称,

他和判断两个二叉树是否相同很类似,然后返回值返回左节点的左和右节点的右 左节点的右和右节点的左递归即可。

🚓6.获取树中结点个数

法一:

int count = 0;
int size1(BTNode root) {if (root == null) {return 0;}count++;size1(root.left);size1(root.right);return count;
}

运用子问题思路来调用递归返回树的总结点个数。

法二:

int count = 0;
int size2(BTNode root) {if (root == null) {return 0;}return size2(root.left) + size2(root.right) + 1;
}

思路:法二的思路和上图一样,例如在 二编号 返回值时,它的值为 编号三 返回的值1加上本身的1,所以 编号二 的值就返回2,同理编号四返回值为3,编号一返回值2+3+1=6。

🚑7.判断一个树是不是完全二叉树:

boolean isCompleteTree(BTNode root) {if (root == null) {return true;}Queue<BTNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {BTNode cur = queue.poll();if (cur != null) {queue.offer(cur.left);queue.offer(cur.right);} else {break;}}while (!queue.isEmpty()) {BTNode top = queue.peek();if (top != null) {return false;}queue.poll();}return true;
}

由上图关系得我们的二叉树不是完全二叉树

如下图如果我们将E的右节点去掉 则我们的二叉树变为了完全二叉树

感谢各位读者的阅读,本文章有任何错误都可以在评论区发表你们的意见,我会对文章进行改正的。如果本文章对你有帮助请动一动你们敏捷的小手点一点赞,你的每一次鼓励都是作者创作的动力哦!😘

相关文章:

Java二叉树面试题讲解

Java二叉树面试题讲解&#x1f697;1.检查两颗树是否相同&#x1f695;2.另一颗树的子树&#x1f699;3.二叉树最大深度&#x1f68c;4.判断一颗二叉树是否是平衡二叉树&#x1f68e;5.对称二叉树&#x1f693;6.获取树中结点个数&#x1f691;7.判断一个树是不是完全二叉树&am…...

rancher2.6进阶之nfs动态创建pv配置

添加NFS client provisioner 动态提供K8s后端存储卷 1.1.前提说明 1.1.1.说明 NFS client provisioner 利用 NFS Server 给 Kubernetes 作为持久存储的后端,并且动态提供PV。 默认 rancher 2 的存储类中的提供者不包含NFS,需要手动添加;添加方式有两种: 1)从应用商店直接安…...

快速上手vue elementUI好看的登录界面

这是一个非常非常适合新手的vue登录界面&#xff0c;总体来说美观大气&#xff0c;axios那部分没有发&#xff0c;有需要的大家可以自己进行二次开发&#xff0c;继续编写。 用到了技术栈有 vue/cli 5.07 element-ui 2.15.9 适合入门级新手&#xff0c;展示下页面 emmm验证码…...

Vue趣味【Vue3+Element Plus+Canvas实现一个简易画板;支持导出为图片】

目录&#x1f31f;前言&#x1f31f;粉丝先看&#x1f31f;创建Vue3项目&#x1f31f;引入Element Plus&#x1f31f;实现代码&#xff08;详细注释&#xff09;&#x1f31f;写在最后&#x1f31f;JSON包里写函数&#xff0c;关注博主不迷路&#x1f31f;前言 哈喽小伙伴们&a…...

【Spring Cloud Alibaba】2.服务注册与发现(Nacos安装)

文章目录环境要求简介安装Nacos源码安装Docker安装数据库配置访问服务我们要搭建一个Spring Cloud Alibaba项目就绕不开Nacos&#xff0c;阿里巴巴提供的Nacos组件&#xff0c;可以提供服务注册与发现和分布式配置服务&#xff0c;拥有着淘宝双十一十几年的流量经验&#xff0c…...

深度学习 Day28——利用Pytorch实现好莱坞明星识别

深度学习 Day28——利用Pytorch实现好莱坞明星识别 文章目录深度学习 Day28——利用Pytorch实现好莱坞明星识别一、前言二、我的环境三、前期工作1、导入依赖项设置GPU2、导入数据集3、划分数据集四、调用官方的VGG16模型五、训练模型1、编写训练函数2、编写测试函数3、设置动态…...

Android中使用FCM进行消息推送

Firebase Cloud Message 的介绍 Firebase Cloud Message(FCM)是由Google推出的一种云端消息推送服务,它是由Google推出的Google Cloud Messaging(GCM)服务的升级版。在2016年5月,Google宣布将Google Cloud Messaging重命名为Firebase Cloud Message,作为Firebase的一部…...

从 X 入门Pytorch——BN、LN、IN、GN 四种归一化层的代码使用和原理

Pytorch中四种归一化层的原理和代码使用前言1 Batch Normalization&#xff08;2015年提出&#xff09;Pytorch官网解释原理Pytorch代码示例2 Layer Normalization&#xff08;2016年提出&#xff09;Pytorch官网解释原理Pytorch代码示例3 Instance Normalization&#xff08;2…...

Windows环境下实施域名访问的一些小知识

文章目录 前言一、windows域名访问流程二、网络域名访问配置设置DNS未正确设置DNS的结果三、本地hosts设置本地hosts本地hosts的优先机制本地hosts的内部访问次序示例一示例二总结前言 作为一种常见的操作系统,windows系统具有其特殊的域名访问管理机制。了解其访问机制,将有…...

78.qt QCustomPlot介绍

参考https://www.qcustomplot.com/index.php/tutorials/settingup 下载地址: https://www.qcustomplot.com/index.php/download 1.添加帮助文档 在QtCreator ——>工具——>选项——>帮助——>文档——>添加,选择qcustomplot.qch文件,确定,以后按F1就能跳转到…...

win32api之文件系统管理(七)

什么是文件系统 文件系统是一种用于管理计算机存储设备上文件和目录的机制。文件系统为文件和目录分配磁盘空间&#xff0c;管理文件和目录的存储和检索&#xff0c;以及提供对它们的访问和共享&#xff0c;以下是常见的两种文件系统&#xff1a; NTFSFAT32磁盘分区容量2T32G…...

点云规则格网化,且保存原始的点云索引

点云规则格网化&#xff0c;且保存原始的点云索引 点云深度学习Voxelize规则&#xff0c;参考PTV2&#xff1a;https://github.com/Gofinge/PointTransformerV2 1总执行文件 import numpy as np import torch from pcr.utils.registry import Registry TRANSFORMS Registry…...

入职第一天就被迫离职,找工作多月已读不回,面试拿不到offer我该怎么办?

大多数情况下&#xff0c;测试员的个人技能成长速度&#xff0c;远远大于公司规模或业务的成长速度。所以&#xff0c;跳槽成为了这个行业里最常见的一个词汇。 前言 前几天&#xff0c;我们一个粉丝跟我说&#xff0c;正常入职一家外包&#xff0c;什么都准备好了&#xff0…...

走进Vue【三】vue-router详解

目录&#x1f31f;前言&#x1f31f;路由&#x1f31f;什么是前端路由&#xff1f;&#x1f31f;前端路由优点缺点&#x1f31f;vue-router&#x1f31f;安装&#x1f31f;路由初体验1.路由组件router-linkrouter-view2.步骤1. 定义路由组件2. 定义路由3. 创建 router 实例4. 挂…...

html+css制作

<!DOCTYPE html> <html><head><meta charset"utf-8"><title>校园官网</title><style type"text/css">*{padding: 0;margin: 0;}#logo{width:30%;float: left;}.nav{width: 100%;height: 100px;background-color…...

Python实现rar、zip和7z文件的压缩和解压

一、7z压缩文件的压缩和解压 1、安装py7zr 我们要先安装py7zr第三方库&#xff1a; pip install py7zr如果python环境有问题&#xff0c;执行上面那一条安装语句老是安装在默认的python环境的话&#xff0c;我们可以执行下面这条语句&#xff0c;将第三方库安装在项目的虚拟…...

从Hive源码解读大数据开发为什么可以脱离SQL、Java、Scala

从Hive源码解读大数据开发为什么可以脱离SQL、Java、Scala 前言 【本文适合有一定计算机基础/半年工作经验的读者食用。立个Flg&#xff0c;愿天下不再有肤浅的SQL Boy】 谈到大数据开发&#xff0c;占据绝大多数人口的就是SQL Boy&#xff0c;不接受反驳&#xff0c;毕竟大…...

RocketMQ 事务消息 原理及使用方法解析

&#x1f34a; Java学习&#xff1a;Java从入门到精通总结 &#x1f34a; 深入浅出RocketMQ设计思想&#xff1a;深入浅出RocketMQ设计思想 &#x1f34a; 绝对不一样的职场干货&#xff1a;大厂最佳实践经验指南 &#x1f4c6; 最近更新&#xff1a;2023年3月24日 &#x…...

为什么 ChatGPT 输出时经常会中断,需要输入“继续” 才可以继续输出?

作者&#xff1a;明明如月学长&#xff0c; CSDN 博客专家&#xff0c;蚂蚁集团高级 Java 工程师&#xff0c;《性能优化方法论》作者、《解锁大厂思维&#xff1a;剖析《阿里巴巴Java开发手册》》、《再学经典&#xff1a;《EffectiveJava》独家解析》专栏作者。 热门文章推荐…...

PyTorch 之 基于经典网络架构训练图像分类模型

文章目录一、 模块简单介绍1. 数据预处理部分2. 网络模块设置3. 网络模型保存与测试二、数据读取与预处理操作1. 制作数据源2. 读取标签对应的实际名字3. 展示数据三、模型构建与实现1. 加载 models 中提供的模型&#xff0c;并且直接用训练的好权重当做初始化参数2. 参考 pyto…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

GraphQL 实战篇:Apollo Client 配置与缓存

GraphQL 实战篇&#xff1a;Apollo Client 配置与缓存 上一篇&#xff1a;GraphQL 入门篇&#xff1a;基础查询语法 依旧和上一篇的笔记一样&#xff0c;主实操&#xff0c;没啥过多的细节讲解&#xff0c;代码具体在&#xff1a; https://github.com/GoldenaArcher/graphql…...

pgsql:还原数据库后出现重复序列导致“more than one owned sequence found“报错问题的解决

问题&#xff1a; pgsql数据库通过备份数据库文件进行还原时&#xff0c;如果表中有自增序列&#xff0c;还原后可能会出现重复的序列&#xff0c;此时若向表中插入新行时会出现“more than one owned sequence found”的报错提示。 点击菜单“其它”-》“序列”&#xff0c;…...

python打卡day49@浙大疏锦行

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 一、通道注意力模块复习 & CBAM实现 import torch import torch.nn as nnclass CBAM(nn.Module):def __init__…...

IP选择注意事项

IP选择注意事项 MTP、FTP、EFUSE、EMEMORY选择时&#xff0c;需要考虑以下参数&#xff0c;然后确定后选择IP。 容量工作电压范围温度范围擦除、烧写速度/耗时读取所有bit的时间待机功耗擦写、烧写功耗面积所需要的mask layer...