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

数据结构------二叉树经典习题1

博主主页: 码农派大星.

关注博主带你了解更多数据结构知识

1判断相同的树 OJ链接


 这道题相对简单,运用我们常规的递归写法就能轻松写出

所以我们解题思路应该这样想:

1.如果p为空,q为空,那么就是两颗空树肯定相等
2.如果一个树为空另一棵树不为空那么一定不相等
3.如果都不为空,值相同才相等。
4.再递归判断左子树是否相等,右子树是否相等,只有左右子树都相等才是相同的树

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {//1,一个为空一个不为空if(p != null && q == null || p == null  && q != null){return false;}//2,第一步走完要么都为空 要么都不为空 两个都是空if(p == null && q== null){return true;}//3,都不为空if(p.val != q.val){return false;}//4,此时代表两个都不为空,同时val也是一样//5,说明根节点相同,接下来判断两棵树的左 右是不是同时相同return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}
}

2判断另一课树的子树OJ链接

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。

这道题也要用到我们的递归思想

1如果都为空树,则false

2如果俩个树为相同的树,则true

3 再递归看sub是否为左子树的子树,右子树的子树,如果都不是,则返回false

class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root == null){return false;}//1,判断两个树是不是相同的树if(isSameTree(root,subRoot)){return true;}//2,if(isSubtree(root.left,subRoot)){return true;}if(isSubtree(root.right,subRoot)){return true;}return false;   }public boolean isSameTree(TreeNode p, TreeNode q) {//1,一个为空一个不为空if(p != null && q == null || p == null  && q != null){return false;}//2,第一步走完要么都为空 要么都不为空 两个都是空if(p == null && q== null){return true;}//3,都不为空if(p.val != q.val){return false;}//4,此时代表两个都不为空,同时val也是一样//5,说明根节点相同,接下来判断两棵树的左 右是不是同时相同return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}}

 

3翻转二叉树OJ链接 

同样的递归思想,不变的套路

1判断是否为空树

2再用递归交换左右树 

class Solution {public TreeNode invertTree(TreeNode root) {if(root == null){return null;}TreeNode tmp = root.left;root.left = root.right;root.right = tmp;invertTree(root.left);invertTree(root.right);return root;}
}

4平衡二叉树OJ链接

 

1判断是否空树

2求左树的深度和右树的深度

3判断左树的深度减右树的深度不能大于1

左树和右数的子树也一样

math.abs() 是一个数学函数,它用于返回一个数的绝对值 

class Solution {public boolean isBalanced(TreeNode root) {if(root == null){return true;}return getHeight(root) >= 1;}//获取二叉树高度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;}if(Math.abs(leftHeight - rightHeight) <= 1){return Math.max(leftHeight,rightHeight) + 1;}else{return -1;}}
}

5对称二叉树 OJ链接

 

1判断是否根节点为空

2 检查结构是否相同:一个为空一个不为空

3检查结构:两个都为空或两个都不为空

4判断左右根节点是否相同

5开始判断是否对称 递归开始:

满足左子树的左  和 右子树的右  对称 同时 左子树的右  和 右子树的左 对称

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){//1检查结构是否相同---一个为空一个不为空if(leftTree != null && rightTree == null || leftTree ==null &&rightTree !=null){return false;}//2检查结构---两个都为空或两个都不为空if(leftTree == null && rightTree == null){return true;}//3检查结狗---- 处理两个都为空或两个都不为空if(leftTree.val != rightTree.val){return false;}//4.此时两个引用都不为空而且节点值一样//5开始判断是否对称//6满足左子树的左  和 右子树的右  对称 同时 左子树的右  和 右子树的左 对称return isSymmetricChild(leftTree.left,rightTree.right)&& isSymmetricChild(leftTree.right,rightTree.left);}
}

 6二叉树的层序遍历OJ链接

我们需要借助队列来实现: 

1判空

2 将root入队列,出队时在让root.left(cur.left)和root.right(cur.right)入队

循环这样的操作,知道队列为空

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> ret = new ArrayList<>();if(root == null){return ret;}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();list.add(cur.val);if(cur.left != null){queue.offer(cur.left);}if(cur.right != null){queue.offer(cur.right);}size--;}ret.add(list);}return ret;}
}

7二叉树的遍历OJ链接 

读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。

 

 1遍历字符串 跳过"#",其他的字符串都new为新Node,此时字符串就是先序遍历的状态

2遍历字符串的时候,我们要把i设置为成员变量防止每次递归后i从0开始

3.遍历二叉树中序输出

import java.util.Scanner;
class TreeNode{public char val;public TreeNode left;public TreeNode right;public TreeNode(char val){this.val = val;}
}
public class Main {public static int i = 0;public static TreeNode createTree(String str){TreeNode root = null;if(str.charAt(i) != '#'){root = new TreeNode(str.charAt(i));i++;root.left = createTree(str);root.right = createTree(str);}else{i++;}return root;}public static void inorder(TreeNode root){if(root == null){return;}inorder(root.left);System.out.print(root.val + " ");inorder(root.right);}public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseString str = in.nextLine();TreeNode root =  createTree(str);inorder(root);}}
}

 

相关文章:

数据结构------二叉树经典习题1

博主主页: 码农派大星. 关注博主带你了解更多数据结构知识 1判断相同的树 OJ链接 这道题相对简单,运用我们常规的递归写法就能轻松写出 所以我们解题思路应该这样想: 1.如果p为空&#xff0c;q为空&#xff0c;那么就是两颗空树肯定相等 2.如果一个树为空另一棵树不为空那么…...

汇聚荣:拼多多长期没有流量如何提高?

在电商的海洋中&#xff0c;拼多多以其独特的团购模式吸引了众多消费者的目光。然而&#xff0c;随着市场竞争的加剧和消费者需求的多样化&#xff0c;一些商家发现自家店铺的流量持续低迷&#xff0c;销售业绩难以突破。面对这样的挑战&#xff0c;如何有效提升拼多多店铺的客…...

Chrome的常用操作总结

Chrome的常用操作总结 最近的自己真的好忙啊,好久真好久没有写博客了,今天我就趁着周末的这段时间总结一下最近自己的用的Chrome浏览器常用的命令 不得不说: 就是特么的丝滑!吊打一切浏览器(不接受反驳哈哈哈)因为反驳我也不听嘻嘻 用好快捷键,就是事半功倍!!!重要的事儿说一遍…...

dvwa靶场 JavaScript Attacks(js攻击)全难度教程(附代码分析)

JS简介 一种解释型语言&#xff08;代码不需要编译&#xff09;&#xff0c;一般镶嵌在html或者php中实现。 JavaScript Attacks&#xff08;Security Level: low&#xff09; 代码分析 <?php $page[ body ] . <<<EOF <script>/* MD5 code from here h…...

Flutter 中的 checkboxListTile 小部件:全面指南

Flutter 中的 checkboxListTile 小部件&#xff1a;全面指南 在Flutter的Material组件库中&#xff0c;CheckboxListTile是一个特殊的ListTile&#xff0c;它内嵌了一个复选框&#xff08;Checkbox&#xff09;。这使得它非常适合用来创建一个带有标题和可选复选框的列表项&am…...

前馈神经网络FNN、多层感知机MLP和反向传播推导

目录 一、前馈神经网络FNN 激活函数的使用 二、多层感知机MLP MLP的典型结构 多层感知机MLP的特点 和前馈神经网络FNN的区别 三、传播推导 1、前向传播(Forward propagation) &#xff08;1&#xff09;输入层到隐藏层 &#xff08;2&#xff09;隐藏层到输出层 2、…...

QML笔记八

QML与C交互 QML中调用C功能、使用QML或者Quick中的C接口、使用C实现自定义的QML对象 注&#xff1a; 只有QObject的派生类才能与QML交互 QML引擎集成Qt元对象系统&#xff0c;QObject的派生子类的属性、方法、信号都可以在QML中访问 C类可以被注册为一个QML实例 C类可以被注册为…...

运维别卷系列 - 云原生监控平台 之 00.prometheus 监控汇总

以下是 运维别卷系列 - 云原生监控平台 相关的详细文章链接&#xff0c;相应的内容&#xff0c;也只是用来做入门使用的 运维别卷系列 - 云原生监控平台 之 01.prometheus 入门和部署运维别卷系列 - 云原生监控平台 之 02.prometheus exporter 实践运维别卷系列 - 云原生监控平…...

信息系统安全与对抗-网络侦查技术与网络扫描技术(期末复习简答题)

1、网络拓扑结构在网络攻击中的作用 查明目标网络的拓扑结构&#xff0c;有利于找到目标网络的关键节点&#xff0c;从而提高攻击效率&#xff0c;达到最大攻击效果。 2、网络侦查在网络攻击中的作用 识别潜在目标系统&#xff0c;确认目标系统适合哪种类型的攻击。 3、百度…...

【python量化交易】—— Alpha选股策略 - Qteasy自定义交易策略【附源码】

使用qteasy创建并回测Alpha选股交易策略 使用qteasy创建并回测Alpha选股交易策略策略思想第一种自定义策略设置方法&#xff0c;使用持仓数据和选股数据直接生成比例交易信号PS信号&#xff1a;第二种自定义策略设置方法&#xff0c;使用PT交易信号设置持仓目标&#xff1a;第三…...

简单记录下:Navicat 导出表结构至 Excel

首先我们需要通过sql语句查询出相关的表结构的结构 SELECT COLUMN_NAME AS 字段名称,COLUMN_TYPE AS 字段类型,IF(IS_NULLABLENO,否,是) AS 是否必填,COLUMN_COMMENT AS 注释FROM INFORMATION_SCHEMA.COLUMNSWHERE table_schema bs-gdsAND table_name sys_menu;查询的结构如下…...

黑马基于Web-socket的java聊天室基本解析

要是用Web-socket协议&#xff0c;我们要前端upgrade升级成web-socket协议 首先我们要引入springboot的websocket起步依赖&#xff0c;这样子方便使用&#xff0c;自己指定版本注意 <dependency><groupId>org.springframework.boot</groupId><artifactId&…...

【操作系统期末速成】​内存管理|内存的装入模块在装入内存的方式|分配管理方式|页面置换算法|页面置换

&#x1f3a5; 个人主页&#xff1a;深鱼~&#x1f525;收录专栏&#xff1a;操作系统&#x1f304;欢迎 &#x1f44d;点赞✍评论⭐收藏 推荐 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到…...

图和网络笔记

文章目录 1. A X 0 AX0 AX02. A T Y 0 A^TY0 ATY03. A X 0 AX0 AX0和 A T Y 0 A^TY0 ATY0的关系 1. A X 0 AX0 AX0 一个图可以由节点和边组成&#xff0c;假设我们有一个节点notes &#xff1a;n4,边edges&#xff1a;m5的有向图&#xff0c;表示如下 通过以上电路…...

请求外部系统报错

报错信息&#xff1a; nested exception is com.google.common.util.concurrent.ExecutionError: java.lang.NoSuchMethodError: com.google.common.net.HostAndPort.getHostText()Ljava/lang/String; 在网上看了好几篇文章&#xff0c;和我的都不符合。 后面自己发现是我的系…...

电路板维修【四】

【开关电源输出电压偏低不稳&#xff0c;用示波器立马锁定故障范围】&#xff1a;https://www.bilibili.com/video/BV1pf421D73K?vd_source3cc3c07b09206097d0d8b0aefdf07958 可以用示波器查看MOS的输出波形来查看其是否损坏&#xff1a; 电源芯片的供电电压来回跳变&#xf…...

(程序设计语言)传值、传引用

1、传值&#xff08;传递值&#xff09;&#xff1a; 在传值的情况下&#xff0c;函数接收到的是参数的一个副本&#xff0c;而不是参数本身。这意味着函数内部对参数的修改不会影响到原始值。传值通常用于基本数据类型&#xff08;如整数、浮点数、布尔值等&#xff09;的传递…...

一次基类类型对象无法被传递问题的分析

看下面一段代码&#xff1a; // proj2.cpp #include <iostream> using namespace std; class CharShape { public:CharShape(char ch) : _ch(ch) {};virtual void Show() 0; protected:char _ch; // 组成图形的字符 }; class Triangle : public CharShape { public:Tr…...

windows设置Redis服务后台自启动

问题 在日常开发过程中&#xff0c;redis是我们常用的缓存工具&#xff0c;但是由于redis对于Linux系统进行开发的&#xff0c;在Linux系统里可以通过修改redis.conf从而从而实现后台启动。 daemonize no 改成 daemonize yes 但是在window上如何也进行后台运行呢&#xff0c…...

掌握Linux常用命令,扫平面试需求障碍

cd 切换目录。 > cd ../ #切换到父级目录 > cd /tmp # 切换到/tmp目录 > cd ~ # 切换到当前用户的家目录 ls命令 查看文件与目录的命令&#xff0c;list 的缩写。 > ls -l #列出长数据串&#xff0c;包含文件的属性与权限数据等 > ls -a #列出隐藏…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

Linux部署私有文件管理系统MinIO

最近需要用到一个文件管理服务&#xff0c;但是又不想花钱&#xff0c;所以就想着自己搭建一个&#xff0c;刚好我们用的一个开源框架已经集成了MinIO&#xff0c;所以就选了这个 我这边对文件服务性能要求不是太高&#xff0c;单机版就可以 安装非常简单&#xff0c;几个命令就…...

Spring Security 认证流程——补充

一、认证流程概述 Spring Security 的认证流程基于 过滤器链&#xff08;Filter Chain&#xff09;&#xff0c;核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤&#xff1a; 用户提交登录请求拦…...

vue3 daterange正则踩坑

<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...

ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]

报错信息&#xff1a;libc.so.6: cannot open shared object file: No such file or directory&#xff1a; #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...