数据结构------二叉树经典习题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);}}
}

 

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

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

相关文章

ROS学习笔记(15)小车巡墙驾驶

0.前提 前一章我讲解了拉氏变换和PID&#xff0c;这一章我来讲解一下小车巡墙驾驶的理论和部分代码。 1.前情回顾 1.拉氏变换 拉普拉斯变换是要将时域问题转换成频域问题来处理。 2.PID控制器 转向角&#xff1a; 误差牺牲&#xff1a; 3.具体参看上一篇文章 2.巡墙驾驶…

游戏理解入门:Rust+Bracket开发一个小游戏

1. Game loop 使用game loop可以使得游戏运行更加流畅和顺滑&#xff0c;它可以&#xff1a; 初始化窗口、图形和其他资源&#xff1b;每当屏幕刷新他都会运行(通常是每秒30,60 )&#xff1b;每次通过循环&#xff0c;他都会调用游戏的tick()函数。 大致的原理流程如下&…

STK中的光照计算模型

本文简要阐述STK中光照计算的模型。 在航天任务中&#xff0c;通常需要分析地面站、飞行器在一定时间内的光照情况&#xff0c;具体包括&#xff1a; 地面站处在光照区和阴影区的具体时间范围&#xff1b;考虑地形遮挡后&#xff0c;地面站的光照区和阴影区的变化情况&#x…

MYSQL-9.问题排查

问题排查的思路与方向 问题排查思路 分析问题&#xff1a;根据理论知识经验分析问题&#xff0c;判断问题可能出现的位置或可能引起问题的原因&#xff0c;将目标缩小到一定范围&#xff1b;排查问题&#xff1a;基于上一步的结果&#xff0c;从引发问题的“可疑性”角度出发…

低空经济:无人机竞赛详解

无人机竞赛市场近年来呈现出蓬勃发展的态势&#xff0c;其市场价值不仅体现在竞赛本身&#xff0c;还体现在推动无人机技术创新、拓展应用场景以及促进产业链发展等多个方面。 一、比赛项目介绍 无人机竞赛通常分为多个项目&#xff0c;包括竞速赛、技巧赛、航拍赛等。每个项目…

新手也能看懂的前端单元测试框架:Vitest

单元测试的概念及作用 1.什么是单元测试&#xff1f; 单元测试是测试中的一个重要环节&#xff0c;它针对软件中的最小可测试单元进行验证&#xff0c;通常是指对代码中的单个函数、方法或模块进行测试。 单元测试旨在确定特定部分代码的行为是否符合预期&#xff0c;通过针…

【谷粒商城】01-环境准备

1.下载和安装VirtualBox 地址&#xff1a;https://www.virtualbox.org/wiki/Downloads 傻瓜式安装VirtualBox 2.下载和安装Vagrant官方镜像 地址&#xff1a;https://app.vagrantup.com/boxes/search 傻瓜式安装 验证是否安装成功 打开CMD,输入vagrant命令&#xff0c;是否…

Linux的常用指令 和 基础知识穿插巩固(巩固知识必看)

目录 前言 ls ls 扩展知识 ls -l ls -a ls -al cd cd 目录名 cd .. cd ~ cd - pwd 扩展知识 路径 / cp [选项] “源文件名” “目标文件名” mv [选项] “源文件名” “目标文件名” rm 作用 用法 ./"可执行程序名" mkdir rmdir touch m…

单位个人怎样向报社的报纸投稿?

作为一名单位的信息宣传员,我肩负着每月定期在媒体上投稿发表文章的重任。然而,在投稿的道路上,我经历了不少波折和挫折。 一开始,我天真地以为只要将稿件发送到报社的投稿邮箱,就能轻松完成任务。然而,现实却远比我想象的复杂。邮箱投稿的竞争异常激烈,编辑们会在众多稿件中挑…

什么是直接内存(NIO)

直接内存不受 JVM 内存回收管理&#xff0c;是虚拟机的系统内存&#xff0c;常见于 NIO 操作时&#xff0c;用于数据 缓冲区&#xff0c;分配回收成本较高&#xff0c;但读写性能高&#xff0c;不受 JVM 内存回收管理。 举例 当上传一个较大文件&#xff08;200M&#xff09;…

【传知代码】VRT: 关于视频修复的模型(论文复现)

前言&#xff1a;随着数字媒体技术的普及&#xff0c;制作和传播视频内容变得日益普遍。但是&#xff0c;视频中由于多种因素&#xff0c;例如传输、存储和录制设备等&#xff0c;经常出现质量上的问题&#xff0c;如图像模糊、噪声干扰和低清晰度等。这类问题对用户的体验和观…

【Ubuntu20.04安装java-8-openjdk】

1 下载 官网下载链接&#xff1a; https://www.oracle.com/java/technologies/downloads/#java8 下载 最后一行 jdk-8u411-linux-x64.tar.gz&#xff0c;并解压&#xff1a; tar -zxvf jdk-8u411-linux-x64.tar.gz2 环境配置 1、打开~/.bashrc文件 sudo gedit ~/.bashrc2、…

【解决】:git clone项目报错fatal: fetch-pack: invalid index-pack output

象&#xff1a;之前一直使用gitee将个人学习和工作相关记录上传到个人gitee仓库&#xff0c;一直没出现过问题。直到有一天换电脑重新拉取代码发现出了问题&#xff0c;具体如下图&#xff1a; 原因分析&#xff1a; 经过查询发现主要原因是因为git clone的远程仓库的项目过大…

NVM安装及VUE创建项目的N种方式

VUE 参考官网&#xff1a;https://cli.vuejs.org/zh/guide/ 目录 NVM安装 1.卸载node.js 2.安装nvm ​编辑​ 3.配置 4.使用nvm安装node.js 5.nvm常用命令 创建VUE项目 1.使用vue init 创建vue2&#xff08;不推荐&#xff09; 2.使用vue create创建vue2和3&#xff…

Docker安装Mosquitto

在物联网项目中&#xff0c;我们经常用到MQTT协议&#xff0c;用MQTT协议做交互就需要部署一个MQTT服务&#xff0c;而mosquitto是一个常用的MQTT应用服务&#xff0c; Mosquitto是一个实现了消息推送协议MQTT v3.1的开源消息代理软件。MQTT&#xff08;Message Queuing Teleme…

knife4j案例

1.导入 <dependency><groupId>com.github.xiaoymin</groupId><artifactId>knife4j-spring-boot-starter</artifactId> </dependency>2.在配置类中加入 knife4j 相关配置并设置静态资源映射&#xff08;否则接口文档页面无法访问&#xff…

大模型LLM 结合联网搜索增强isou

参考&#xff1a; https://github.com/yokingma/search_with_ai 在线使用网址&#xff1a; https://isou.chat/ 安装github下载&#xff0c;运行docker compose 如果一直报下面错误&#xff1a; 解决方法https://github.com/yokingma/search_with_ai/pull/7 默认打开&a…

【PG数据库】PostgreSQL 日志归档详细操作流程

1.1 日志归档的目的 pg数据库日志归档是将PostgreSQL数据库的日志文件进行归档的过程。 归档的主要目的是为了保留历史数据&#xff0c;确保数据的一致性和完整性&#xff0c;同时为数据恢复提供必要的支持。 pg数据库日志归档的目的包括&#xff1a; 1.数据恢复&#xff1…

[链表专题]力扣141, 142

1. 力扣141 : 环形链表 题 : 给你一个链表的头节点 head &#xff0c;判断链表中是否有环。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;则链表中存在环。 为了表示给定链表中的环&#xff0c;评测系统内部使用整数 pos 来表示链表尾…

洛谷P1364 医院设置

P1364 医院设置 题目描述 设有一棵二叉树&#xff0c;如图&#xff1a; 其中&#xff0c;圈中的数字表示结点中居民的人口。圈边上数字表示结点编号&#xff0c;现在要求在某个结点上建立一个医院&#xff0c;使所有居民所走的路程之和为最小&#xff0c;同时约定&#xff0c…