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

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

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

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

FFmpeg:Windows系统小白安装及其使用

一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】&#xff0c;注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录&#xff08;即exe所在文件夹&#xff09;加入系统变量…...

高考志愿填报管理系统---开发介绍

高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发&#xff0c;采用现代化的Web技术&#xff0c;为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## &#x1f4cb; 系统概述 ### &#x1f3af; 系统定…...

车载诊断架构 --- ZEVonUDS(J1979-3)简介第一篇

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 做到欲望极简,了解自己的真实欲望,不受外在潮流的影响,不盲从,不跟风。把自己的精力全部用在自己。一是去掉多余,凡事找规律,基础是诚信;二是…...

JS红宝书笔记 - 3.3 变量

要定义变量&#xff0c;可以使用var操作符&#xff0c;后跟变量名 ES实现变量初始化&#xff0c;因此可以同时定义变量并设置它的值 使用var操作符定义的变量会成为包含它的函数的局部变量。 在函数内定义变量时省略var操作符&#xff0c;可以创建一个全局变量 如果需要定义…...

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡 背景 我们以建设星云智控官网来做AI编程实践&#xff0c;很多人以为AI已经强大到不需要程序员了&#xff0c;其实不是&#xff0c;AI更加需要程序员&#xff0c;普通人…...