算法的学习笔记—二叉树中和为某一值的路径

img

😀前言
在二叉树中寻找和为某一特定值的路径问题是一个经典的面试题,考察了对二叉树的遍历能力以及递归和回溯算法的理解和应用。本文将详细解析这一问题,并提供一个Java实现。

🏠个人主页:尘觉主页

文章目录

  • 😄二叉树中和为某一值的路径
    • 🥰问题描述
    • 💖解题思路
    • 😀Java代码实现
      • 代码解析
      • 时间复杂度分析
    • 😄总结

😄二叉树中和为某一值的路径

🥰问题描述

给定一棵二叉树和一个整数,要求找出所有从树的根结点开始,到叶结点结束,结点值的和等于给定整数的路径。路径定义为从根节点开始一直到叶子节点所经过的所有节点。

例如,下面的二叉树有两条路径的节点值之和为 22:

ed77b0e6-38d9-4a34-844f-724f3ffa2c12

路径分别是:

  • 10 -> 5 -> 7
  • 10 -> 12

💖解题思路

要解决这个问题,可以使用深度优先搜索(DFS)结合回溯法进行路径的遍历与选择。核心思想是从根节点开始,逐步减去当前节点的值,如果在到达叶子节点时,剩余的值刚好为0,则找到了一个符合条件的路径。以下是详细的实现步骤:

  1. 递归遍历树:从根节点开始,递归地遍历左子树和右子树。
  2. 回溯法:在递归过程中,记录当前路径,并在递归返回时将路径回溯,即将最后一个节点移除,这样可以在不同的路径中复用同一个路径列表。
  3. 判断条件:在每次递归中,检查当前节点是否为叶子节点且路径的节点值之和是否等于目标值,如果是,则将当前路径记录下来。

😀Java代码实现

import java.util.ArrayList;class TreeNode {int val;  // 当前节点的值TreeNode left;  // 左子节点TreeNode right;  // 右子节点TreeNode(int x) { val = x; }
}public class Solution {private ArrayList<ArrayList<Integer>> ret = new ArrayList<>();  // 用于存储所有符合条件的路径/*** 主函数,用于查找所有路径* @param root 根节点* @param target 目标和* @return 返回所有路径的列表*/public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {backtracking(root, target, new ArrayList<>());  // 从根节点开始进行回溯return ret;  // 返回结果集}/*** 回溯函数,递归查找路径* @param node 当前节点* @param target 剩余的目标和* @param path 当前路径*/private void backtracking(TreeNode node, int target, ArrayList<Integer> path) {if (node == null) {return;  // 如果当前节点为空,直接返回}path.add(node.val);  // 将当前节点值加入路径target -= node.val;  // 更新目标值,减去当前节点的值// 判断是否达到目标值且当前节点为叶子节点if (target == 0 && node.left == null && node.right == null) {ret.add(new ArrayList<>(path));  // 如果满足条件,将当前路径加入结果集} else {// 递归处理左子树backtracking(node.left, target, path);// 递归处理右子树backtracking(node.right, target, path);}// 回溯,移除路径中的最后一个节点path.remove(path.size() - 1);}
}

代码解析

  • ret:保存所有符合条件的路径,是一个包含多个路径的列表。
  • FindPath:主函数,初始化递归过程并返回结果。
  • backtracking:核心递归函数。参数 node 为当前处理的节点,target 为剩余需要匹配的值,path 保存当前路径。

在每次递归中,首先判断当前节点是否为 null,如果是,则直接返回。否则,将节点值加入当前路径并更新目标值。若目标值为0且当前节点为叶子节点,则将当前路径加入结果集中。最后一步是回溯,将当前路径中的最后一个节点移除,继续尝试其他路径。

时间复杂度分析

该算法的时间复杂度主要取决于二叉树的深度和每个节点的访问次数。最坏情况下,需要遍历二叉树的每一条路径,其复杂度为 O(N),其中 N 是树中节点的数量。

😄总结

通过本文的讲解,相信大家对如何在二叉树中寻找和为某一特定值的路径有了更加深入的理解。通过深度优先搜索和回溯法,我们可以有效地解决这一问题。Java实现中的递归思路清晰且简洁,适用于面试中的二叉树相关问题。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了,如果有什么疑问的地方请指出,诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力,今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下,创造不易您们的支持是我的动力🤞

img

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/407590.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

使用Node-RED实现和部署物联网入侵检测的机器学习管道

整理自 《Implementing and Deploying an ML Pipeline for IoT Intrusion Detection with Node-RED》&#xff0c;由 Yimin Zhang 等人撰写&#xff0c;发表于 2023 年 CPS-IoT Week Workshops。以下是根据提供的 PDF 内容整理的论文的详细主要内容&#xff1a; 摘要 (Abstra…

0基础深度学习项目13:基于TensorFolw实现天气识别

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 目录 一、创建环境二、前期准备2.1 设置GPU2.2 导入数据2.3 数据预处理2.3.1 加载数据2.3.2 查看图像的标签 2.4 数据可视化 三、构建简单的CNN网络&#xff0…

KT来袭,打造沉浸式体验的聚合性web3应用平台

随着步入 2024&#xff0c;漫长的区块链熊市即将接近尾声。纵观产业发展&#xff0c;逆流而上往往会是彰显品牌市场影响力和技术实力的最佳证明。在这次周期中&#xff0c;一个名为KT的web3.0聚合平台吸引了市场关注&#xff0c;无论在市场层面还是技术层面&#xff0c;都广泛赢…

Leetcode 104. 二叉树的最大深度 C++实现

Leetcode 104. 二叉树的最大深度 问题&#xff1a;给定一个二叉树root&#xff0c;返回其最大深度。 二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* …

培训第三十五天(容器的基础命令使用)

1、创建一个容器并同时执行echo命令 # 快速启动一个容器执行特定的一次性命令并查看输出结果&#xff0c;输出结果后容器直接退出[rootdocker ~]# docker run -it --namea0 centos:latest echo "abc"abc[rootdocker ~]# docker psCONTAINER ID IMAGE COMMAND …

游戏app激励视频广告预加载位置,最大化广告收益

最近收到很多游戏类App开发者咨询激励视频广告&#xff0c;在帮助开发者分析产品的时候&#xff0c;特别是一些初级开发者的App产品&#xff0c;发现用户进入这些App&#xff0c;或者打开某个功能时就弹出激励视频广告&#xff0c;这样是违规的&#xff0c;并且用户看完广告也是…

使用gitee存储项目

gitee地址&#xff1a;Gitee - 基于 Git 的代码托管和研发协作平台 创建gitee远程仓库 将远程仓库内容拉取到本地仓库 复制下面这个地址 通过小乌龟便捷推送拉取代码&#xff1a;https://blog.csdn.net/m0_65520060/article/details/140091437

数字图像处理【15】特征检测——SIFT特征检测

一、引入SIFT算法 上一篇文章我们重温学习了Harris角点检测算法的基本原理&#xff0c;但在实际生产使用Harris检测角点的时候&#xff0c;会发现一个问题&#xff0c;就是用于检测的输入图像的尺寸大小会直接影响到Harris的检测结果。这是为什么呢&#xff1f;主要是Harris角…

2024最新50道NLP和人工智能领域面试题+答案(中文+英文双版本)

编者按&#xff1a;分享一个很硬核的免费人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c; 可以当故事来看&#xff0c;轻松学习。 中文版本 自然语言处理 (NLP)已成为语言学、人工智能和计算机科学交叉领域的变革性领域。随着文本数据量的不断增加&…

内网横向移动常用方法

横向移动 #横向移动含义 横向移动是以已经被攻陷的系统为跳板&#xff0c;通过收集跳板机的信息&#xff08;文档&#xff0c;存储的凭证&#xff0c;ipc连接记录等等信息&#xff09;来访问其他域内主机。#常见横向手段 1&#xff0c;通过相同的用户名密码批量ipc连接其他域内…

【学习笔记】Day 22

一、进度概述 1、机器学习常识23-24&#xff0c;以及相关代码复现 2、python 补完计划&#xff08;详见 python 专题&#xff09; 二、详情 23、U-Net 从宏观结构上来讲&#xff08;以下摘自常识23&#xff09;&#xff1a; U-Net 就是 U 形状的网络, 前半部分 (左边…

三星计划今年HBM4设计,2025年初开始样品测试

三星计划今年晚些时候完成首款HBM4内存设备的设计定稿&#xff0c;2025年初开始样品测试 根据nN Elec援引行业消息人士的报道&#xff0c;三星计划在今年晚些时候完成首款HBM4内存设备的设计定稿&#xff0c;并预计将于2025年初开始样品测试。该公司预计将采用其最新一代10纳米…

详细分析 el-progress的基本知识以及用法(附Demo)

目录 前言1. 基本知识2. Demo3. 实战 前言 由于实战项目中有所引用&#xff0c;对此记录基本的知识点&#xff0c;并且以Demo的形式呈现 1. 基本知识 el-progress 是 Element Plus UI 库中的一个进度条组件&#xff0c;用于显示任务的完成情况 可以帮助用户了解某个操作或任…

[数据集][目标检测]工程机械车辆检测数据集VOC+YOLO格式3189张10类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;3189 标注数量(xml文件个数)&#xff1a;3189 标注数量(txt文件个数)&#xff1a;3189 标注…

密码生成器(HTML+CSS+JavaScript)

&#x1f30f;个人博客主页&#xff1a;心.c ​ 前言&#xff1a;前两天写了密码生成器&#xff0c;现在跟大家分享一下&#xff0c;大家如果想使用随便拿&#xff0c;如果哪里有问题还请大佬们给我指出&#xff0c;感谢支持 &#x1f525;&#x1f525;&#x1f525;专题文章&…

Vue3集成高德离线地图实践

1. 离线地图效果预览 2. 地图下载器下载离线地图 根据需要选择地图&#xff0c;我这边选择高德地图&#xff0c;层级选择0-15级别即可&#xff0c;进行下载 3. 放到nginx内网服务器 注意配置允许跨域 4. Vue3核心代码 // main.js // 初始化vue-amap initAMapApiLoader({o…

Android自定义简单TextView

自定义属性 <declare-styleable name"TextView"><!--name 属性名称format 格式&#xff1a;string 文字 color颜色dimension 宽高 字体大小 integer数字reference 资源引用(drawable)--><attr name"YiRanText" format"string"/&…

torchvision中的数据集使用

1.数据集&#xff1a; 自定义数据集transforms中的类 如何将数据集和transforms结合在一起&#xff1f; 以CIFAR10为列 2.CIFAR10数据集的下载与导入 import torchvisiontrain_settorchvision.datasets.CIFAR10(root"./dataset",trainTrue,downloadTrue) test_set…

判别分析2|Bayes判别分析|Fisher判别分析|软件求解

Bayes判别分析 引入先验信息 距离判别只要求知道总体的数字特征&#xff0c;不涉及总体的分布函数 当均值和协方差未知时&#xff0c;就用样本的均值和协方差矩阵做估计值。距离判别方法简单实用&#xff0c;但没有考虑到每个总体出现的机会大小&#xff0c;即先验概率&#…

Git的使用教程及常用语法03

七.如何从版本库中删除文件 第一种方式&#xff1a;直接在工作区删除文件&#xff0c;然后提交 rm ffile1.txt (注意&#xff1a;这个不是git命令&#xff0c;而是linux命令) 看到状态发现&#xff0c;文件file1.txt已经被删除&#xff0c;提示需要提交到暂存区。 因为我们只…