当前位置: 首页 > 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) 模型,它建立在以前…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

k8s从入门到放弃之HPA控制器

k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率&#xff08;或其他自定义指标&#xff09;来调整这些对象的规模&#xff0c;从而帮助应用程序在负…...

实战设计模式之模板方法模式

概述 模板方法模式定义了一个操作中的算法骨架&#xff0c;并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下&#xff0c;重新定义算法中的某些步骤。简单来说&#xff0c;就是在一个方法中定义了要执行的步骤顺序或算法框架&#xff0c;但允许子类…...

Spring Boot + MyBatis 集成支付宝支付流程

Spring Boot MyBatis 集成支付宝支付流程 核心流程 商户系统生成订单调用支付宝创建预支付订单用户跳转支付宝完成支付支付宝异步通知支付结果商户处理支付结果更新订单状态支付宝同步跳转回商户页面 代码实现示例&#xff08;电脑网站支付&#xff09; 1. 添加依赖 <!…...

二维FDTD算法仿真

二维FDTD算法仿真&#xff0c;并带完全匹配层&#xff0c;输入波形为高斯波、平面波 FDTD_二维/FDTD.zip , 6075 FDTD_二维/FDTD_31.m , 1029 FDTD_二维/FDTD_32.m , 2806 FDTD_二维/FDTD_33.m , 3782 FDTD_二维/FDTD_34.m , 4182 FDTD_二维/FDTD_35.m , 4793...

数据分析六部曲?

引言 上一章我们说到了数据分析六部曲&#xff0c;何谓六部曲呢&#xff1f; 其实啊&#xff0c;数据分析没那么难&#xff0c;只要掌握了下面这六个步骤&#xff0c;也就是数据分析六部曲&#xff0c;就算你是个啥都不懂的小白&#xff0c;也能慢慢上手做数据分析啦。 第一…...