DFS算法专题(一)——二叉树中的深搜【回溯与剪枝的初步注入】
目录
1、DFS算法简介
2、算法实战应用【leetcode】
2.1 计算布尔二叉树的值
2.1.1 算法原理
2.1.2 算法代码
2.2 求根节点到叶节点数字之和
2.2.1 算法原理
2.2.2 算法代码
2.3 二叉树剪枝
2.3.1 算法原理
2.3.2 算法代码
2.4 验证二叉搜索树
2.4.1 算法原理
2.4.2 算法代码
2.5 二叉搜索树中第K小的元素
2.5.1 算法原理
2.5.2 算法代码
2.6 二叉树的所有路径
2.6.1 算法原理
2.6.2 算法代码
1、DFS算法简介
DFS,全称为 Depth First Traversal,深度优先遍历。
DFS算法是在树或者图这样的数据结构中常用的一种遍历算法。这个算法会尽可能深的搜索树或者图的分支,直到⼀条路径上的所有节点都被遍历完毕,然后再回溯到上一层,继续寻找另外一条路遍历。
简单来说,DFS就是:优先考虑深度,换句话说就是一条路走到黑,直到无路可走的情况下,才会选择回头,然后重新选择一条路。
在二叉树中,常见的深度优先遍历有:前序遍历、中序遍历以及后序遍历。
2、算法实战应用【leetcode】
2.1 计算布尔二叉树的值
. - 力扣(LeetCode)
2.1.1 算法原理
- 以宏观角度看待递归
- 后序遍历拿到最终值
- 函数头:boolean dfs(root);
- 宏观思想-->函数体:返回左子树的布尔值,返回右子树的布尔值,根据当前根节点返回最终结果
- 函数出口:叶子节点,根据叶子节点数值返回布尔类型值
2.1.2 算法代码
/*** 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 evaluateTree(TreeNode root) {if(root.left == null) return root.val == 0 ? false : true;boolean left = evaluateTree(root.left);boolean right = evaluateTree(root.right);return root.val == 2 ? left || right : left && right;}
}
2.2 求根节点到叶节点数字之和
. - 力扣(LeetCode)
2.2.1 算法原理
- 递归的过程中,我们需要传递上层以及本层节点数字之和preSum
- 将上层以及本层节点数字之和preSum传递给当前根节点的左右子树
- 返回左右子树数值之和
- 函数出口:叶子节点。注意:要先将叶子节点的数值注入总和之中再返回
2.2.2 算法代码
/*** 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 sumNumbers(TreeNode root) {return dfs(root, 0);}public int dfs(TreeNode root, int preSum) {preSum = preSum * 10 + root.val;if(root.left == null && root.right == null) return preSum;int ret = 0;//剪枝if(root.left != null) ret += dfs(root.left, preSum);if(root.right != null) ret += dfs(root.right, preSum);return ret;}
}
2.3 二叉树剪枝
. - 力扣(LeetCode)
2.3.1 算法原理
- 思想:后序遍历,当根节点的左右子树的所有值均为0时,才可删除当前树
- 从叶子节点开始判断,若其值为0则可删除
- 可被删除的节点返回null,父节点.left/right接收null,修改其父节点的指向
- 继续判断当前节点
2.3.2 算法代码
/*** 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 TreeNode pruneTree(TreeNode root) {if(root == null) return null;root.left = pruneTree(root.left);root.right = pruneTree(root.right);if(root.left == null && root.right == null && root.val == 0) return null;else return root;}
}
2.4 验证二叉搜索树
. - 力扣(LeetCode)
2.4.1 算法原理
本题所用思想:
- 全局变量 int prev = Long.MIN_VALUE;(记录上一个节点的值)
- 中序遍历(将当前根节点依次和prev比较,查看序列是否有序)
- 需当前节点的左子树与右子树均满足二叉搜索树,以及当前节点本身满足二叉搜索树,才能说明该树为二叉搜索树
- 若当前节点满足,则更新prev的值为当前节点的val值;若当前节点不满足,则返回false,再通过剪枝优化代码,使函数提前终止并返回false。
2.4.2 算法代码
/*** 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 {long prev = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if(root == null) return true;boolean left = isValidBST(root.left);if(prev >= root.val) {return false;}prev = root.val;boolean right = isValidBST(root.right);return left && right;}
}
2.5 二叉搜索树中第K小的元素
. - 力扣(LeetCode)
2.5.1 算法原理
与上一题思想一致,因为是二叉搜索树,所以中序遍历是突破口:
- 设置两个全局变量:public int count+public int ret
- 中序遍历(通过有序序列查找目标值)
- 因为中序遍历得到的是一个有序序列,所以利用count计数,计到第k个数时,使用ret存入
- 得到目标值后,在通过剪枝优化函数,使递归返回
2.5.2 算法代码
/*** 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 count;public int ret;public int kthSmallest(TreeNode root, int k) {count = k;dfs(root);return ret;}public void dfs(TreeNode root) {//count == 0 -> 剪枝if(root == null || count == 0) return;dfs(root.left);count--;if(count == 0) {ret = root.val;//剪枝return;}dfs(root.right);}
}
2.6 二叉树的所有路径
. - 力扣(LeetCode)
2.6.1 算法原理
本题使用思想:
- 设置全局变量:List<String> ret;
- 回溯 -> “恢复现场”
- 注意:本题不能使用全局变量path恢复现场,因为本层路径的修改会影响到上一层。解法:使用局部变量(函数传参)path,回溯到上一层时,函数会自动“恢复现场”。
- 剪枝 -> 优化代码
函数设计:
- 函数头:void dfs(root,path);
- 函数体:非叶子:root.val+"->" ;叶子:root.val + ret.add(path) + return(剪枝)
- 函数出口 -> 剪枝处理
2.6.2 算法代码
/*** 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 {List<String> ret = new ArrayList<>();public List<String> binaryTreePaths(TreeNode root) {//path -> 记录路径//回溯 -> 函数自动“恢复现场”dfs(root, new StringBuffer());return ret;}public void dfs(TreeNode root, StringBuffer path_) {//保留上一层路径StringBuffer path = new StringBuffer(path_);path.append(root.val);if(root.left == null && root.right == null) {ret.add(path.toString());return;}path.append("->");//if -> 剪枝,省略函数出口if(root.left != null) dfs(root.left, path);if(root.right != null) dfs(root.right, path);}
}
END
相关文章:

DFS算法专题(一)——二叉树中的深搜【回溯与剪枝的初步注入】
目录 1、DFS算法简介 2、算法实战应用【leetcode】 2.1 计算布尔二叉树的值 2.1.1 算法原理 2.1.2 算法代码 2.2 求根节点到叶节点数字之和 2.2.1 算法原理 2.2.2 算法代码 2.3 二叉树剪枝 2.3.1 算法原理 2.3.2 算法代码 2.4 验证二叉搜索树 2.4.1 算法原理 …...

AWS SES服务 Golang接入教程(排坑版)
因为刚来看的时候 也迷迷糊糊的 所以 先讲概念 再上代码 一 基础设置 这里需要完成两个最基础的设置任务 1 是验证至少一个收件电子邮箱 2 【很关键】是验证发送域。即身份里的域类型的身份。(可以理解为配置你的域名邮箱服务器(SMPT)为亚马…...

Vite + Vue3 +Vant4出现Toast is not a function
今天写前端的时候出现了这个问题搞了我一会 搜集原因: 1:是vant版本的问题,Toast()的方法是vant3版本的写法,而我用的是vant4,vant4中的写法改成了showToast()方法,改正过来 import {showToast} from "vant"; 发现还是…...

【MATLAB】模拟退火算法
模拟退火算法的MATLAB实现 模拟退火算法简介模拟退火算法应用实例关于计算结果 模拟退火算法简介 1982年,Kirkpatrick 将退火思想引入组合优化领域,提出了一种能够有效解决大规模组合优化问题的算法,尤其对 NP 完全问题表现出显著优势。模拟…...
什么是Kubernetes RBAC?
什么是Kubernetes RBAC? 1、什么是RBAC?2、核心组件3、优势💖The Begin💖点点关注,收藏不迷路💖 在Kubernetes集群中,RBAC(基于角色的访问控制)是保障系统安全的关键。它通过角色和绑定管理不同实体对资源的访问权限,具有显著优势: 1、什么是RBAC? RBAC是Kube…...
在Spring Boot中通过自定义注解、反射以及AOP(面向切面编程)
在Spring Boot中,通过自定义注解、反射以及AOP(面向切面编程)来动态修改请求参数是一种高级且强大的技术组合,它允许开发者在不修改原始方法实现的情况下,对方法的执行过程进行干预和定制。这种技术通常用于日志记录、…...

安防监控视频平台LntonAIServer视频智能分析平台新增视频质量诊断功能
随着安防行业的快速发展,视频监控系统已经成为维护公共安全和个人隐私的重要工具。然而,由于各种因素的影响,视频流的质量可能会受到影响,从而导致监控效果不佳。为了解决这一问题,LntonAIServer推出了全新的视频质量诊…...

vscode从本地安装插件
1. 打开VSCode。 2. 点击左侧菜单中的“扩展”(或按CtrlShiftX)。 3. 点击“更多操作”(三个点)> “从VSIX安装”。 4. 选择下载的.vsix文件。 5. 点击“安装”即可安装插件。...

Superset二次开发之新增复选框Checkbox筛选器
一. 背景 Superset目前支持的筛选类型:值、数值范围、时间列、时间粒度、时间范围 5种类型,显然无法满足业务需求。根据产品需要,需要支持复选框、单选框、级联选择等类型的筛选器。本文探讨复选框、单选框的技术实现方式。 二. 效果预览 三. 实现思路 复用 值 筛选器模块,…...
PromQL 语法
什么是 PromQL PromQL (Prometheus Query Language) 是 Prometheus 监控系统中用于查询时间序列数据的语言。它允许用户编写查询,以从 Prometheus 中检索并处理监控数据。 PromQL 的基础概念 1. 时间序列 Prometheus 中的时间序列由以下几个部分组成:…...
掌握Go语言中的时间与日期操作
Go语言中的时间与日期操作 在编写程序时,处理时间和日期看似是一项无关紧要的任务,但在需要同步多个任务或从文本文件中读取时间时,它的重要性便凸显出来。Go语言中的time包为我们提供了丰富的时间与日期操作功能。本文将详细介绍如何在Go语…...

4G模块、WIFI模块、NBIOT模块通过AT指令连接华为云物联网服务器(MQTT协议)
MQTT协议概述 MQTT(Message Queuing Telemetry Transport)是一种轻量级的消息传输协议,它被设计用来提供一对多的消息分发和应用之间的通讯,尤其适用于远程位置的设备和高延迟或低带宽的网络。MQTT协议基于客户端-服务器架构&…...
spring数据校验Validation
文章目录 需要的依赖创建校验对象Validator 需要的依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-validation</artifactId> </dependency>创建校验对象Validator 测试的实体类 //创建…...

Uniapp基于uni拦截器+Promise的请求函数封装
最近在学Uniapp,到封装请求的时候本来还想用axios,但是看到一些教学视频有更简单的方法, 基于uni的拦截器和Promise封装的请求函数 但是他们是用TS写的,还没学到TS,我就把JS写了,最终也是请求成功 // src/…...

【工具】使用 Jackson 实现优雅的 JSON 格式化输出
说明 在 Java 开发中,我们经常需要处理 JSON 数据。无论是从服务器端返回的数据,还是本地存储的数据,JSON 格式都因其轻量级和易于解析的特点而被广泛使用。当我们需要查看或调试 JSON 数据时,优雅、格式化的输出将大大提高我们的…...

ApacheKafka中的设计
文章目录 1、介绍1_Kafka&MQ场景2_Kafka 架构剖析3_分区&日志4_生产者&消费者组5_核心概念总结6_顺写&mmap7_Kafka的数据存储形式 2、Kafka的数据同步机制1_高水位(High Watermark)2_LEO3_高水位更新机制4_副本同步机制解析5_消息丢失问…...
.NET 自定义过滤器 - ActionFilterAttribute
这个代码片段定义了一个自定义的 ASP.NET Core 过滤器(GuardModelStateAttribute),用于在控制器动作执行之前验证模型状态(ModelState)。如果模型状态无效,则构造一个 ProblemDetails 对象来描述错误&#…...

VMware Fusion Pro 13 for Mac虚拟机软件
Mac分享吧 文章目录 效果一、下载软件二、开始安装安装完成!!! 效果 一、下载软件 下载软件 地址:www.macfxb.cn 二、开始安装 安装完成!!!...

HarmonyOS应用开发环境搭建
本文主要讲述的是HarmonyOS应用开发环境的搭建,HUAWEI DevEco Studio是基于IntelliJ IDEA Community开源版本打造,为运行在HarmonyOS系统上的应用和服务提供一站式的开发平台。具体下载链接DevEco Studio 一、下载 DevEco Studio 只需要下载对应的版本&…...

YOLOv8改进实战 | 注意力篇 | 引入ICCV2023顶会LSKNet:大选择性卷积注意力模块LSKA,助力小目标检测
YOLOv8专栏导航:点击此处跳转 前言 YOLOv8 是由 YOLOv5 的发布者 Ultralytics 发布的最新版本的 YOLO。它可用于对象检测、分割、分类任务以及大型数据集的学习,并且可以在包括 CPU 和 GPU 在内的各种硬件上执行。 YOLOv8 是一种尖端的、最先进的 (SOTA) 模型,它建立在以前…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...

RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...

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

【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
Java - Mysql数据类型对应
Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...