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

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 算法原理 

  1. 以宏观角度看待递归
  2. 后序遍历拿到最终值
  3. 函数头:boolean dfs(root);
  4. 宏观思想-->函数体:返回左子树的布尔值,返回右子树的布尔值,根据当前根节点返回最终结果
  5. 函数出口:叶子节点,根据叶子节点数值返回布尔类型值

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 算法原理

  1. 递归的过程中,我们需要传递上层以及本层节点数字之和preSum
  2. 将上层以及本层节点数字之和preSum传递给当前根节点的左右子树
  3. 返回左右子树数值之和
  4. 函数出口:叶子节点。注意:要先将叶子节点的数值注入总和之中再返回

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 算法原理

  1. 思想:后序遍历,当根节点的左右子树的所有值均为0时,才可删除当前树
  2. 从叶子节点开始判断,若其值为0则可删除
  3. 可被删除的节点返回null,父节点.left/right接收null,修改其父节点的指向
  4. 继续判断当前节点

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 算法原理 

本题所用思想: 

  1. 全局变量 int prev = Long.MIN_VALUE;(记录上一个节点的值)
  2. 中序遍历(将当前根节点依次和prev比较,查看序列是否有序)
  3. 需当前节点的左子树与右子树均满足二叉搜索树,以及当前节点本身满足二叉搜索树,才能说明该树为二叉搜索树
  4. 若当前节点满足,则更新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 算法原理

 与上一题思想一致,因为是二叉搜索树,所以中序遍历是突破口: 

  1. 设置两个全局变量:public int count+public int ret
  2. 中序遍历(通过有序序列查找目标值)
  3. 因为中序遍历得到的是一个有序序列,所以利用count计数,计到第k个数时,使用ret存入
  4. 得到目标值后,在通过剪枝优化函数,使递归返回

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 算法原理

本题使用思想: 

  1. 设置全局变量:List<String> ret;
  2. 回溯 -> “恢复现场”
  3. 注意:本题不能使用全局变量path恢复现场,因为本层路径的修改会影响到上一层。解法:使用局部变量(函数传参)path,回溯到上一层时,函数会自动“恢复现场”。
  4. 剪枝 -> 优化代码

函数设计:

  • 函数头: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 【很关键】是验证发送域。即身份里的域类型的身份。&#xff08;可以理解为配置你的域名邮箱服务器&#xff08;SMPT&#xff09;为亚马…...

Vite + Vue3 +Vant4出现Toast is not a function

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

【MATLAB】模拟退火算法

模拟退火算法的MATLAB实现 模拟退火算法简介模拟退火算法应用实例关于计算结果 模拟退火算法简介 1982年&#xff0c;Kirkpatrick 将退火思想引入组合优化领域&#xff0c;提出了一种能够有效解决大规模组合优化问题的算法&#xff0c;尤其对 NP 完全问题表现出显著优势。模拟…...

什么是Kubernetes RBAC?

什么是Kubernetes RBAC? 1、什么是RBAC?2、核心组件3、优势💖The Begin💖点点关注,收藏不迷路💖 在Kubernetes集群中,RBAC(基于角色的访问控制)是保障系统安全的关键。它通过角色和绑定管理不同实体对资源的访问权限,具有显著优势: 1、什么是RBAC? RBAC是Kube…...

在Spring Boot中通过自定义注解、反射以及AOP(面向切面编程)

在Spring Boot中&#xff0c;通过自定义注解、反射以及AOP&#xff08;面向切面编程&#xff09;来动态修改请求参数是一种高级且强大的技术组合&#xff0c;它允许开发者在不修改原始方法实现的情况下&#xff0c;对方法的执行过程进行干预和定制。这种技术通常用于日志记录、…...

安防监控视频平台LntonAIServer视频智能分析平台新增视频质量诊断功能

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

vscode从本地安装插件

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

Superset二次开发之新增复选框Checkbox筛选器

一. 背景 Superset目前支持的筛选类型:值、数值范围、时间列、时间粒度、时间范围 5种类型,显然无法满足业务需求。根据产品需要,需要支持复选框、单选框、级联选择等类型的筛选器。本文探讨复选框、单选框的技术实现方式。 二. 效果预览 三. 实现思路 复用 值 筛选器模块,…...

PromQL 语法

什么是 PromQL PromQL (Prometheus Query Language) 是 Prometheus 监控系统中用于查询时间序列数据的语言。它允许用户编写查询&#xff0c;以从 Prometheus 中检索并处理监控数据。 PromQL 的基础概念 1. 时间序列 Prometheus 中的时间序列由以下几个部分组成&#xff1a;…...

掌握Go语言中的时间与日期操作

Go语言中的时间与日期操作 在编写程序时&#xff0c;处理时间和日期看似是一项无关紧要的任务&#xff0c;但在需要同步多个任务或从文本文件中读取时间时&#xff0c;它的重要性便凸显出来。Go语言中的time包为我们提供了丰富的时间与日期操作功能。本文将详细介绍如何在Go语…...

4G模块、WIFI模块、NBIOT模块通过AT指令连接华为云物联网服务器(MQTT协议)

MQTT协议概述 MQTT&#xff08;Message Queuing Telemetry Transport&#xff09;是一种轻量级的消息传输协议&#xff0c;它被设计用来提供一对多的消息分发和应用之间的通讯&#xff0c;尤其适用于远程位置的设备和高延迟或低带宽的网络。MQTT协议基于客户端-服务器架构&…...

spring数据校验Validation

文章目录 需要的依赖创建校验对象Validator 需要的依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-validation</artifactId> </dependency>创建校验对象Validator 测试的实体类 //创建…...

Uniapp基于uni拦截器+Promise的请求函数封装

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

【工具】使用 Jackson 实现优雅的 JSON 格式化输出

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

ApacheKafka中的设计

文章目录 1、介绍1_Kafka&MQ场景2_Kafka 架构剖析3_分区&日志4_生产者&消费者组5_核心概念总结6_顺写&mmap7_Kafka的数据存储形式 2、Kafka的数据同步机制1_高水位&#xff08;High Watermark&#xff09;2_LEO3_高水位更新机制4_副本同步机制解析5_消息丢失问…...

.NET 自定义过滤器 - ActionFilterAttribute

这个代码片段定义了一个自定义的 ASP.NET Core 过滤器&#xff08;GuardModelStateAttribute&#xff09;&#xff0c;用于在控制器动作执行之前验证模型状态&#xff08;ModelState&#xff09;。如果模型状态无效&#xff0c;则构造一个 ProblemDetails 对象来描述错误&#…...

VMware Fusion Pro 13 for Mac虚拟机软件

Mac分享吧 文章目录 效果一、下载软件二、开始安装安装完成&#xff01;&#xff01;&#xff01; 效果 一、下载软件 下载软件 地址&#xff1a;www.macfxb.cn 二、开始安装 安装完成&#xff01;&#xff01;&#xff01;...

HarmonyOS应用开发环境搭建

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

YOLOv8改进实战 | 注意力篇 | 引入ICCV2023顶会LSKNet:大选择性卷积注意力模块LSKA,助力小目标检测

YOLOv8专栏导航:点击此处跳转 前言 YOLOv8 是由 YOLOv5 的发布者 Ultralytics 发布的最新版本的 YOLO。它可用于对象检测、分割、分类任务以及大型数据集的学习,并且可以在包括 CPU 和 GPU 在内的各种硬件上执行。 YOLOv8 是一种尖端的、最先进的 (SOTA) 模型,它建立在以前…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; 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&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 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&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 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 配置文件,主要包含以下几个部…...