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

算法通过村第8关【青铜】| 二叉树的经典算法题

二叉树的双指针

1.相同的树

思路:递归的挨个比较是否相同

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if((p == null&&q!=null) || (p != null && q == null) || (p!=null&&q!=null&&p.val != q.val)){return false;}if(p == q && p == null){return true;}boolean left = isSameTree(p.left,q.left);boolean right = isSameTree(p.right,q.right);return left&&right;}}

 2.对称二叉树

思路:分别判断左边对称和右边对称即可

class Solution {public boolean isSymmetric(TreeNode root) {return trace(root.left,root.right);}public boolean trace(TreeNode left,TreeNode right) {if(left == null && right!=null){return false;}if(left != null && right==null){return false;}if(left == right){return true;}if(left.val != right.val){return false;}boolean l = trace(left.left,right.right);boolean r = trace(left.right,right.left);return l&&r;}}

 3.合并二叉树

思路:递归三部曲

第一步:确定参数和返回值

显而易见,本题需要同步遍历两颗二叉树,TreeNode trace(TreeNode root1, TreeNode root2)

第二步:确定结束条件

当遇到root2为空或者root1为空就不需要再向下递归找相加了

第三步:确定单层逻辑

当root1和root2不为空,则两值相加

 当root2为空,直接返回root1

当root1为空,直接返回root2

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {return trace(root1,root2);}public TreeNode trace(TreeNode root1, TreeNode root2) {if(root2 == null){return root1;}if(root1 != null && root2!=null){root1.val = root1.val + root2.val;}if(root1 == null && root2!= null){return root2;}root1.left = trace(root1.left,root2.left);root1.right = trace(root1.right,root2.right);return root1;}}

路径专题

1.二叉树的所有路径

思路:

第一步:确定参数和返回值

题目要求从根结点到叶子结点的所有路径,只需要下一个结点和字符串记录 

void trace(TreeNode root,StringBuilder r)

第二步:确定结束条件

也就是什么时候找完一条路径,也就是什么时候找到叶子结点,也就是左右孩子都为空

第三步:确定单层逻辑

保存路径上的结点

class Solution { List<String> res = new LinkedList<>();public List<String> binaryTreePaths(TreeNode root) {String r = "";trace(root,r);return res;}public void trace(TreeNode root,String r){if(root == null){return;}r = r + root.val;     if(root.left == null && root.right == null){res.add(r);return;}r = r+"->";trace(root.left,r);trace(root.right,r);}
}

2.路径总和

思路:递归三部曲

第一步:确定参数和返回值

题目要求找到是否有一条路径符合要求,返回boolean,需要参数记录路径之和还有目标值

boolean hasPathSum(TreeNode root,int res,int targetSum)

 第二步:确定终止条件

当找到一条路径就结束

第三步:确定单层逻辑

当前路径求和

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {int res = 0;return hasPathSum(root,res,targetSum);}public boolean hasPathSum(TreeNode root,int res,int targetSum){if(root == null){return false;}res += root.val;if(root.left == null && root.right == null){if(res == targetSum){return true;}return false;}boolean left = hasPathSum(root.left,res,targetSum);boolean right = hasPathSum(root.right,res,targetSum);return left || right;}
}

翻转

思路:递归三部曲

第一步: 确定参数和返回值

翻转二叉树需要两两交换左右结点,遍历每一个结点进行交换即可。即参数root返回void

第二步:确定结束条件

结点为空

第三步:确定单层逻辑

每一个结点交换左右子树

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

相关文章:

算法通过村第8关【青铜】| 二叉树的经典算法题

二叉树的双指针 1.相同的树 思路&#xff1a;递归的挨个比较是否相同 class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if((p null&&q!null) || (p ! null && q null) || (p!null&&q!null&&p.val ! q.val)){return f…...

Open3D 点云均值滤波

目录 一、算法原理1、均值滤波2、参考文献二、代码实现三、结果展示本文由CSDN点云侠原创,原文链接。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫。 一、算法原理 1、均值滤波 对待处理的当前采样点,选择一个模板,该模板由其邻近的若干个数据点组成,…...

C语言指针入门详解

一、指针简介 指针(Pointer)是C语言的一个重要知识点&#xff0c;其使用灵活、功能强大&#xff0c;是C语言的灵魂指针与底层硬件联系紧密&#xff0c;使用指针可操作数据的地址&#xff0c;实现数据的间接访问指针就是地址&#xff0c;通过访问此地址来获取该地址存储的数据 …...

软件工程(十四) 设计模式之结构型模式(二)

1、组合模式 简要说明 将对象组合成树形结构以表示“整体-部分”的层次结构,使得用户对单个对象和组合对象的使用具有一致性。 速记关键字 树形目录结构 类图如下 由类图其实可以看出,组合模式就是将具有父子关系的结构,组装形成一棵树,并且根据规范,树干节点和叶子节…...

不解压的方式直接更新jar包内部的内容

前言 如果线上直接更新一个class&#xff0c;可以不用解压&#xff0c;直接利用jar命令直接更新jar报的资源和内容 更新jar包内容文件 Jar 工具提供了一个 u 选项&#xff0c;你可以通过修改其清单或添加文件来更新现有 JAR 文件的内容。 添加文件的基本命令具有以下格式&am…...

软件工程(八) UML之类图与对象图

1、类图与对象图 1.1、类图与对象图的概念 类图(class diagram)描述一组类、接口、协作和它们之间的关系 对象图(object diagram)描述一组对象及它们之间的关系、对象图描述了在类图中所建立的事物实例的静态快照。 1.2、类图与对象图的区别 类图和对象图基本上是一样…...

【Unity3D赛车游戏】【五】Unity中汽车加速效果是如何优化的?

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 秩沅 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a;Uni…...

龙智案例:某大型零售企业如何打造高速、现代化的ITSM体系

在2023 DevOps国际峰会北京站的现场&#xff0c;我们对话了龙智咨询顾问胡若愚&#xff0c;他为我们奖助了一位零售业的大型客户是如何在数字化浪潮中&#xff0c;凭借龙智提供的Jira Service Management产品及服务&#xff0c;打造现代化ITSM平台&#xff0c;提升客户满意度。…...

jdk 03.stream

01.集合处理数据的弊端 当我们在需要对集合中的元素进行操作的时候&#xff0c;除了必需的添加&#xff0c;删除&#xff0c;获取外&#xff0c;最典型的操作就是集合遍历 package com.bobo.jdk.stream; import java.util.ArrayList; import java.util.Arrays; import java.ut…...

“华为杯”研究生数学建模竞赛2018年-【华为杯】C题:对恐怖袭击事件记录数据的量化分析

目录 摘 要: 一、 问题背景与重述 1.1 问题背景 1.2 问题重述 二、 问题分析...

java8的reduce方法

在 Java 8 中&#xff0c;reduce 是一个流操作方法&#xff0c;用于将流中的元素按照指定的操作进行归约&#xff08;reduce&#xff09;操作&#xff0c;最终得到一个结果。 reduce 方法有三种重载形式&#xff1a; T reduce(T identity, BinaryOperator<T> accumulato…...

Mac发现有的软件不能上网的破解之法

1、Mac上打开终端 terminal &#xff0c;获取 root 权限。 sudo -i 2、编辑 hosts 文件 vim /private/etc/hosts 3、找到被禁止软件的数据请求域名&#xff0c;然后删除相关行&#xff0c;快捷件dd&#xff0c;然后:wq保存退出 比如百度 127.0.0.1 pan.baidu.com ##sec 印…...

定时检测接口是否正常飞书告警脚本

第一版 支持多个接口地址,循环检测,定时每分钟执行一次脚本 告警效果 脚本 飞书机器人创建忽略跳过,各大协作平台大同小异拿出机器人hook地址 #!/bin/bash URL_LIST=(https://gatewaxxxxxxxxxxxxxxxxxx https://sandbox-gatexxxxxxxxxxxxxxxxxx)for URL in ${URL_LIST[*...

【MySQL】2、MySQL数据库的管理

常用 describe user; Field:字段名称 Type:数据类型 Null :是否允许为空 Key :主键 Type:数据类型 Null :是否允许为空key :主键 Default :默认值 Extra :扩展属性&#xff0c;例如:标志符列&#xff08;标识了种子&#xff0c;增量/步长&#xff09;1 2 id&#xff1a;1 3 5 …...

8086汇编test指令学习

Test指令将两个操作数进行逻辑与运算&#xff0c;并根据运算结果设置相关的标志位。Test的两个操作数不会被改变。运算结果在设置过相关标记位后会被丢弃。 TEST AX,BX 与 AND AX,BX 命令有相同效果&#xff0c;只是Test指令不改变AX和BX的内容&#xff0c;而AND指令会把结果保…...

简单js逆向案例(2)

文章目录 前文分析完整代码结尾 前文 本文章中所有内容仅供学习交流&#xff0c;严禁用于商业用途和非法用途&#xff0c;否则由此产生的一切后果均与作者无关&#xff0c;若有侵权&#xff0c;请联系我立即删除&#xff01; 分析 目标网址 aHR0cHM6Ly9zZWFyY2guYmlkY2VudGV…...

azure data studio SQL扩展插件开发笔记

node.js环境下拉取脚手架 npm install -g yo generator-azuredatastudio yo azuredatastudio 改代码 运行 调试扩展&#xff0c;在visual studio code中安装插件即可 然后visual studio code打开进行修改运行即可 image.png 运行后自动打开auzre data studio了&#xff0c; 下面…...

【二分】搜索旋转数组

文章目录 不重复数组找最小值&#xff0c;返回下标重复数组找最小值&#xff0c;返回下标不重复数组找target&#xff0c;返回下标重复数组找target&#xff0c;返回bool重复数组找target&#xff0c;返回下标 不重复数组找最小值&#xff0c;返回下标 class Solution {public …...

APSIM模型应用与参数优化、批量模拟

APSIM (Agricultural Production Systems sIMulator)模型是世界知名的作物生长模拟模型之一。APSIM模型有Classic和Next Generation两个系列模型&#xff0c;能模拟几十种农作物、牧草和树木的土壤-植物-大气过程&#xff0c;被广泛应用于精细农业、水肥管理、气候变化、粮食安…...

QT使用QXlsx实现对Excel sheet的相关操作 QT基础入门【Excel的操作】

准备:搭建环境引用头文件QT中使用QtXlsx库的三种方法 QT基础入门【Excel的操作】_吻等离子的博客-CSDN博客 #include "xlsxdocument.h"QTXLSX_USE_NAMESPACE // 添加Xlsx命名空间(https://github.com/dbzhang800/QtXlsxWriter) or QXLSX_USE_NAMESPACE // 添加Xl…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

python打卡day49

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

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...