数据结构(Java):力扣牛客 二叉树面试OJ题(一)
👉 目录 👈
1、题一:检查两棵树是否相同
1.1 思路分析
1.2 代码
2、题二:另一棵树的子树
2.1 思路分析
2.2 代码
3、题三:翻转二叉树
3.1 思路分析
3.2 代码
4、题四:判断树是否对称
4.1 思路分析
4.2 代码
5、题五:判断是否为平衡二叉树
5.1 思路分析
5.1.1 平衡二叉树概念
5.1.2 思路一 O(n^2)
5.1.3 思路一代码
5.1.4 思路二 :改善为O(n)【字节跳动面试题】
5.1.5 思路二代码
6、题六:将二叉搜索树转化为有序的双向链表
6.1 二叉搜索树的性质
6.2 思路分析
6.3 代码
7、题七:二叉树的遍历和构建
7.1 思路分析
7.2 代码
1、题一:检查两棵树是否相同
. - 力扣(LeetCode)
1.1 思路分析
两棵树相同,需要注意以下几点:
- 两棵树结构相同,若结构不相同,那两棵树必然是不相同的
- 在结构相同的前提下,还需满足节点值相同
- 若结构和节点值都相同,那么两棵树相同
额外注意的是:若两棵树为空,那么也是相同的。
我们可以按照子问题遍历的思想,当左子树和右子树中全部节点同时满足以上条件,说明两棵树相等。
1.2 代码
时间复杂度:O(min(m,n))
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;}//走到这里,说明两棵树的结构相同且不为空,那判断他们的节点值即可//若节点值不相同,则说明两棵树不相同,返回falseif(p.val != q.val) {return false;}//递归遍历//左右两棵子树必须同时满足条件 //才能说明两棵树才相同return isSameTree(p.left,q.left) &&isSameTree(p.right,q.right);}
}
2、题二:另一棵树的子树
. - 力扣(LeetCode)
2.1 思路分析
一棵树的子树 需要满足:
- 这棵子树包括主树的某个节点,和这个节点的所有后代节点
- 这棵树自身,也可看做自己的子树
了解子树概念后,我们可以按照以下思路解决问题:
- 判断子树根节点subRoot和主树根节点root是否相同
- 若相同,则调用检查两棵树是否相同的方法(题一),若相同,则为子树
- 若不相同,继续遍历,判断子树是否和root的左子树相同
- 若不相同,继续遍历,判断子树是否和root的右子树相同
- 递归解决问题
2.2 代码
时间复杂度:O(m*n)
因为最坏的情况下:
每个节点和子树值相同,但判断树是否相同时,总是最后一个节点不相同
/**时间复杂度为:O(m*n)因为最坏的情况下:每个节点和子树值相同,但判断树是否相同时,总是最后一个节点不相同
*/
class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {//如果递归到空,说明没有找到子树,返回falseif(root == null) {return false;}//判断当前节点的整颗树和子树是否相同即可if(isSameTree(root,subRoot)) {return true;}//如果递归遇见了子树 则一路返回trueif(isSubtree(root.left,subRoot)) return true;if(isSubtree(root.right,subRoot)) return true;//本次递归没有找见子树 返回falsereturn false;}public boolean isSameTree(TreeNode p, TreeNode q) {// 1.先判断结构是否是一样的if (p != null && q == null || p == null && q != null) {return false;}// 上述if语句 如果没有执行,意味着两个引用 同时为空 或者同时不为空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);}
}
3、题三:翻转二叉树
. - 力扣(LeetCode)
3.1 思路分析
这道题的思路很简单,就是:将每个节点的左右子树进行交换。
我们可以以前序遍历思想遍历所有节点,在访问当前树的根节点时将其左右子树进行交换。
3.2 代码
根据解题思想,很清晰的分析出时间复杂度为:O(n)
class Solution {public TreeNode invertTree(TreeNode root) {if(root == null) {return null;}//交换左右子树swapNode(root);invertTree(root.left);invertTree(root.right);return root;}public void swapNode(TreeNode root) {TreeNode tmp = root.left;root.left = root.right;root.right = tmp;}
}
4、题四:判断树是否对称
. - 力扣(LeetCode)
4.1 思路分析
要判断这颗树是对称的,
- 就要判断,根节点的左子树和右子树是对称的
- 要判断根节点的左子树和右子树是对称的 ,需要左右子树的结构相同;在结构相同前提下,节点的值要相同
- 如果结构相同了,值也相同了,那么要递归去判断:左子树的左树和右子树的右树是否轴对称(是否结构相同、值相同);以及左子树的右树和右子树的左树是否轴对称(是否结构相同、值相同)。(均满足)
- 我们只能递归来一个节点一个节点的去遍历,去判断,去比较
4.2 代码
class Solution {public boolean isSymmetric(TreeNode root) {if(root == null) {return true;}return isSymmetricChild(root.left,root.right);}public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {//空树对称if(leftTree == null && rightTree == null) {return true;}//结构不相同 必定不对称if(leftTree != null && rightTree == null || leftTree == null && rightTree != null) {return false;}//节点值不相同 必定不对称if(leftTree.val != rightTree.val) {return false;}//左子树的左树和右子树的右树 //左子树的右树和右子树的左树//都要对称return isSymmetricChild(leftTree.left,rightTree.right) && isSymmetricChild(leftTree.right,rightTree.left);}
}
5、题五:判断是否为平衡二叉树
. - 力扣(LeetCode)
5.1 思路分析
5.1.1 平衡二叉树概念
如果一棵树是平衡二叉树,那么满足:
- 树中所有节点的左右子树高度差<=1
- 也就是说,每一棵子树都是平衡二叉树
根据平衡二叉树的概念,我们有以下两种思路解决问题。
5.1.2 思路一 O(n^2)
- 递归遍历所有节点,求出每个节点的左右子树高度差,若出现>=2的情况,立即返回false
- 当前节点的左树上的节点和右树上的节点全部满足高度差<=1 时,说明为平衡二叉树
- 该思路时间复杂度为O(n^2),求根节点高度的方法时间复杂度本来就为O(n),而要求得所有节点的高度,时间复杂度就为O(n^2)
5.1.3 思路一代码
class Solution {public boolean isBalanced(TreeNode root) {//空树 平衡if(root == null) {return true;}//当前节点左子树高度int h1 = getHeight(root.left);//当前节点右子树高度int h2 = getHeight(root.right);int h = Math.abs(h1-h2);//高度差//不平衡if(h >= 2) return false;//左子树和右子树同时平衡 说明整棵树平衡return isBalanced(root.left) &&isBalanced(root.right);}public int getHeight(TreeNode root) {if (root == null) {return 0;}int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);//树的高度为 左子树高度和右子树高度的最大值+节点自身的1个高度return leftHeight > rightHeight? leftHeight + 1: rightHeight + 1;}
}
5.1.4 思路二 :改善为O(n)【字节跳动面试题】
思路一虽然能解决问题,但时间复杂度达到了O(n^2),并且产生了很多次重复的计算,例如:圈中节点的高度,在计算它祖先的高度时就被计算了多次,产生了很多重复的计算。
如果要将时间复杂度改善为O(n),该如何完成呢?
O(n)思路分析:
- 我们可以只求根节点的高度
- 在求节点高度时,我们使用递归遍历思想,返回的是左右子树高度的最大值+1(左右子树最大高度+节点自身1个高度)
- 而我们可以将求高度的方法进行改善,在递归过程中,一旦发现左右子树高度差绝对值>=2时(说明不平衡),立即返回负数(标记,其他标记也可);如果高度差绝对值<=1时(说明平衡),返回正常的高度值即可。如若发现返回的是负数,立即一路返回负数。
- 最终判断方法的返回值即可,若为负数,则说明该树不平衡;若为正数(高度值),说明该树平衡。
5.1.5 思路二代码
class Solution {/**时间复杂度:O(n)*/public boolean isBalanced(TreeNode root) {if(root == null) {return true;}//负数说明该树不平衡return getHeight(root) > 0;}public int getHeight(TreeNode root) {if (root == null) {return 0;}int leftHeight = getHeight(root.left);//如若发现返回的是负数,则说明该树一定不平衡,一路返回负数if(leftHeight < 0) {return -1;}//如若发现返回的是负数,则说明该树一定不平衡,一路返回负数int rightHeight = getHeight(root.right);if(rightHeight < 0) {return -1;}//如果绝对值<=1 说明当前树平衡,返回高度值if(Math.abs(leftHeight - rightHeight) <= 1) {return Math.max(leftHeight , rightHeight) + 1;}else {//否则返回负数return -1;}}
}
6、题六:将二叉搜索树转化为有序的双向链表
二叉搜索树与双向链表_牛客题霸_牛客网
6.1 二叉搜索树的性质
二叉搜索树,又称二叉排序树、二叉查找树,具有以下性质:
- 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
- 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
- 二叉搜索树可以为空树
- 以中序遍历来遍历一棵二叉搜索树,那么得到的序列就是一个有序的升序序列。
6.2 思路分析
以中序遍历递归这棵二叉搜索树,将得到的根节点依次连接(修改其左右指针),得到的就是排好序的双向链表。
- 借助中序遍历思想递归,遍历各个节点,修改指向
- 将每个节点的left域当做双向链表中的prev域,将right域当做next域
- 借助一个成员变量prev,存储上一个节点的地址,完成各节点指向的修改和连接
6.3 代码
时间复杂度:O(n)
public class Solution {//定义一个成员变量 存储上一个节点的地址TreeNode prev;//初始值为nullpublic void ConvertNode(TreeNode pRootOfTree) {if(pRootOfTree == null) return;//中序遍历思想递归ConvertNode(pRootOfTree.left);//修改前驱,将当前节点的left域更改为前一个节点的地址pRootOfTree.left = prev;if (prev != null) {//当prev不为空时,修改后继//将其right域修改为当前节点的地址(prev本就是当前节点的前驱)prev.right = pRootOfTree;}//更新prevprev = pRootOfTree;ConvertNode(pRootOfTree.right);}public TreeNode Convert(TreeNode pRootOfTree) {if (pRootOfTree == null) {return null;}ConvertNode(pRootOfTree);TreeNode head = pRootOfTree;//找头结点//转换成双向链表后,链表的头结点就在pRootOfTree的左边//头结点的left(前驱)为nullwhile(head.left != null) {head = head.left;}return head;}
}
7、题七:二叉树的遍历和构建
二叉树遍历_牛客题霸_牛客网
7.1 思路分析
我们知道,如果仅仅根据一个遍历方式的结果是无法构建出一棵二叉树的,必须有两个遍历方式且必须包含中序遍历。
而这道题是不同的,因为题目给出的遍历结果包含了空树,所以仅仅利用一个遍历方式我们就可以构建出二叉树。
只要构建出这棵二叉树,我们再使用中序遍历递归打印节点值就可以了。
难点在,如何使用代码根据前序遍历来构建二叉树?
思路如下:
- 题目仅仅给出了main方法,意味着我们要自己创建节点,创建的节点类要满足树中节点的要求,包含val域(char类型)、left域、right域,同时要给出构造方法
- 创建二叉树,肯定是要遍历前序遍历结果的字符串(这里以静态i成员遍历字符串)
- 给出的是前序遍历结果,所以要以前序遍历的思想递归来创建树
- 如果遍历到的字符不是'#',说明不是空树,实例出该值的节点,i++(此时仅仅实例节点,各节点间并没有连接)
- 创建左子树,创建右子树
- 如果遇到的字符是'#',说明遇到是空树,i++,返回空节点(递归回退),上一个节点的left或者right接收
- 如果节点的左子树或者右子树创建完成,递归回退,上一个节点的left或者right接收
- 如果节点的左子树和右子树都创建完成(本次递归函数结束),递归回退,上一个节点的left或者right接收
- 也就是说,我们在递归回退的过程中,完成节点之间的连接
- 最后一步,以中序遍历形式来访问根节点并打印
注意:这里因为题目条件限制,只能使用静态成员i来遍历字符串。但是对于我们实际的应用,不建议使用静态成员,因为当创建多个对象时,他们都会使用并改变i的值,而创建二叉树时,必须从0下标处遍历字符串!!!
7.2 代码
import java.util.Scanner;//节点
class TreeNode {TreeNode left;TreeNode right;char val;public TreeNode(char val) {this.val = val;}
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 case//防止有多组测试用例,每次使用时i要置0Main.i = 0;String str = in.nextLine();TreeNode root = creatTree(str);InOrder(root);}}public static int i;public static TreeNode creatTree(String str) {TreeNode node = null;if (str.charAt(i) != '#') {//不是空树,就实例化该值的节点node = new TreeNode(str.charAt(i));i++;//在递归回退的过程中,完成节点之间的连接node.left = creatTree(str);node.right = creatTree(str);} else {//是空树,i++i++;}return node;}//中序遍历,打印根节点public static void InOrder(TreeNode root) {if (root == null) {return;}InOrder(root.left);System.out.print(root.val + " ");InOrder(root.right);}
}
相关文章:

数据结构(Java):力扣牛客 二叉树面试OJ题(一)
👉 目录 👈 1、题一:检查两棵树是否相同 1.1 思路分析 1.2 代码 2、题二:另一棵树的子树 2.1 思路分析 2.2 代码 3、题三:翻转二叉树 3.1 思路分析 3.2 代码 4、题四:判断树是否对称 …...

在国产芯片上实现YOLOv5/v8图像AI识别-【1.3】YOLOv5的介绍及使用(训练、导出)更多内容见视频
本专栏主要是提供一种国产化图像识别的解决方案,专栏中实现了YOLOv5/v8在国产化芯片上的使用部署,并可以实现网页端实时查看。根据自己的具体需求可以直接产品化部署使用。 B站配套视频:https://www.bilibili.com/video/BV1or421T74f 数据…...

逻辑门的题目怎么做?
FPGA语法练习——二输入逻辑门,一起来听~~ FPGA语法练习——二输入逻辑门 题目介绍:F学社-全球FPGA技术提升平台 (zzfpga.com)...

CentOS 7报错:yum命令报错 “ Cannot find a valid baseurl for repo: base/7/x86_6 ”
参考连接: 【linux】CentOS 7报错:yum命令报错 “ Cannot find a valid baseurl for repo: base/7/x86_6 ”_centos linux yum search ifconfig cannot find a val-CSDN博客 Centos7出现问题Cannot find a valid baseurl for repo: base/7/x86_64&…...

51单片机STC89C52RC——18.1 HC-SR04超声波测距
目的/效果 独立按键K1按下后开始测距,LCD显示距离(mm) 一,STC单片机模块 二,HC-SR04 超声波测距 2.1 HC-SR04 简介 HC-SR04超声波测距模块提供2cm~400cm的测距功能,精度达3mm。 2.2 时序 以上时序图表明…...
WordPress与 wp-cron.php
WordPress 傲居全球最流行的内容管理系统(CMS)之位,占据了互联网约43%的网站后台,这主要得益于其直观易用的用户界面以及丰富的扩展功能,特别是为新手用户提供了极大的便利。 然而,在畅享WordPress带来的便…...

bb-------
社保费申报及缴纳...

数据挖掘与分析部分实验与实训项目报告
一、机器学习算法的应用 1. 朴素贝叶斯分类器 相关代码 import pandas as pd from sklearn.model_selection import train_test_split from sklearn.naive_bayes import GaussianNB, MultinomialNB from sklearn.metrics import accuracy_score # 将数据加载到DataFrame中&a…...
Python中使用SpeechLib实现文本转换语音朗读的示例(修正bug)
一、修正SpeechLib的导入包顺序后的代码: from comtypes.client import CreateObjectengine CreateObject(SAPI.SpVoice) stream CreateObject(SAPI.SpFileStream)from comtypes.gen import SpeechLibinfile E:\\语音文档\\易经64卦读音.txt outfile E:\\demo.…...

政安晨【零基础玩转各类开源AI项目】基于Ubuntu系统部署Hallo :针对肖像图像动画的分层音频驱动视觉合成
政安晨的个人主页:政安晨 欢迎 👍点赞✍评论⭐收藏 收录专栏: 零基础玩转各类开源AI项目 希望政安晨的博客能够对您有所裨益,如有不足之处,欢迎在评论区提出指正! 本文目标:在Ubuntu系统上部署Hallo&#x…...

Spring Boot1(概要 入门 Spring Boot 核心配置 YAML JSR303数据校验 )
目录 一、Spring Boot概要 1. SpringBoot优点 2. SpringBoot缺点 二、Spring Boot入门开发 1. 第一个SpringBoot项目 项目创建方式一:使用 IDEA 直接创建项目 项目创建方式二:使用Spring Initializr 的 Web页面创建项目 (了解&#…...

电脑屏幕录制怎么弄?分享3个简单的电脑录屏方法
在信息爆炸的时代,屏幕上的每一个画面都可能成为我们生活中不可或缺的记忆。作为一名年轻男性,我对于录屏软件的需求可以说是既挑剔又实际。今天,我就为大家分享一下我近期体验的三款录屏软件:福昕录屏大师、转转大师录屏大师和OB…...

idea双击没有反应,打不开
问题描述 Error opening zip file or JAR manifest missing : /home/IntelliJ-IDEA/bin/jetbrains-agent.jar解决方案...
关于UniApp使用的个人笔记
UniApp 开发者中心 用于注册应用以及申请对应证书 https://dev.dcloud.net.cn/pages/app/list https://blog.csdn.net/fred_kang/article/details/124988303 下载证书后,获取SHA1关键cmd keytool -list -v -keystore test.keystore Enter keystore password…...
autoware.universe源码略读(3.16)--perception:object_range_splitter
autoware.universe源码略读3.16--perception:object_range_splitter Overviewnode(Class Constructor)ObjectRangeSplitterNode::ObjectRangeSplitterNode(mFunc)ObjectRangeSplitterNode::objectCallback Overview 这里处理的依…...
深度学习落地实战:人脸五官定位检测
前言 大家好,我是机长 本专栏将持续收集整理市场上深度学习的相关项目,旨在为准备从事深度学习工作或相关科研活动的伙伴,储备、提升更多的实际开发经验,每个项目实例都可作为实际开发项目写入简历,且都附带完整的代码与数据集。可通过百度云盘进行获取,实现开箱即用 …...

270-VC709E 基于FMC接口的Virtex7 XC7VX690T PCIeX8 接口卡
一、板卡概述 本板卡基于Xilinx公司的FPGA XC7VX690T-FFG1761 芯片,支持PCIeX8、两组 64bit DDR3容量8GByte,HPC的FMC连接器,板卡支持各种FMC子卡扩展。软件支持windows,Linux操作系统。 二、功能和技术指标: 板卡功…...

【go】Excelize处理excel表 带合并单元格、自动换行与固定列宽的文件导出
文章目录 1 简介2 相关需求与实现2.1 导出带单元格合并的excel文件2.2 导出增加自动换行和固定列宽的excel文件 1 简介 之前整理过使用Excelize导出原始excel文件与增加数据校验的excel导出。【go】Excelize处理excel表 带数据校验的文件导出 本文整理使用Excelize导出带单元…...
uniapp自定义tabBar
uniapp自定义tabBar 1、在登录页中获取该用户所有的权限 getAppFrontMenu().then(res>{if(res.length > 0){// 把所有权限存入缓存中let firstPath res.reverse()[0].path;uni.setStorageSync(qx_data, res);uni.switchTab({url: firstPath,})// 方法二 通过uni.setTabB…...

IDEA2023版本创建JavaWeb项目及配置Tomcat详细步骤!
一、创建JavaWeb项目 第一步 之前的版本能够在创建时直接选成Web项目,但是2023版本在创建项目时没有该选项,需要在创建项目之后才能配置,首先先创建一个项目。 第二步 在创建好的项目中选中项目后(一定要注意选中项目名称然后继…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...

python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...

云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...

群晖NAS如何在虚拟机创建飞牛NAS
套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...