【算法刷题 | 二叉树 06】4.10( 路径总和、路径总和 || )

在这里插入图片描述

文章目录

  • 13.路径总和
    • 13.1问题
    • 13.2解法一:递归
      • 13.2.1递归思路
        • (1)确定递归函数参数以及返回值
        • (2)确定终止条件
        • (3)确定递归逻辑
      • 13.2.2代码实现
  • 14.路径总和 ||
    • 14.1问题
    • 14.2解法一:递归
      • 14.2.1递归思路
        • (1)确定递归函数参数以及返回值
        • (2)确定终止条件
        • (3)确定递归逻辑
      • 14.2.2代码实现

13.路径总和

13.1问题

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false

叶子节点 是指没有子节点的节点。

  • 示例一:

img

输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出:true
解释:等于目标和的根节点到叶节点路径如上图所示。

13.2解法一:递归

13.2.1递归思路

(1)确定递归函数参数以及返回值
  • 参数:节点、计数器(记录从根节点到该节点的值)、targetSum
  • 返回值:需要搜索整棵二叉树并且需要处理递归返回值的递归函数就需要返回值,此题使用boolean代表这颗树是否存在路径总和为targetSum的路径
private boolean traversal(TreeNode node,int count,int targetSum)
(2)确定终止条件
  • 当当前节点为叶子节点并且count=targetSum时,返回true(该count已经包含当前节点的值了);
  • 当当前节点为叶子节点,直接返回false
if(node.left==null && node.right==null && count==targetSum){
	return true;
}
if(node.left==null && node.right==null){
	return false;
}
(3)确定递归逻辑
  • 因为终止条件是判断叶子节点,所以递归的过程中就不要让空节点进入递归了;
  • 若该节点的左右孩子非空,则递归(注意递归函数的count加上左右孩子的值);
  • 递归完若发现为true,则直接返回true,否则进行回溯,不要该左孩子节点(count减去该值),进行右孩子节点的查找(回溯);
if(node.left!=null){
	if(traversal(node.left,count+=node.left.val,targetSum)){
        return true;
    }
    //回溯
    count-=node.left.val;
}
if(node.right!=null){
	if(traversal(node.right,count+=node.right.val,targetSum)){
        return true;1
    }
    //回溯
    count-=node.right.val;
}
return false;

13.2.2代码实现

public boolean hasPathSum(TreeNode root, int targetSum) {

        if(root==null){
            return false;
        }
        return traversal(root,root.val,targetSum);
    }

    private boolean traversal(TreeNode node,int count,int targetSum){
        if(node.left==null && node.right==null && count==targetSum){
	        return true;
        }
        
        if(node.left==null && node.right==null){
	        return false;
        }

        if(node.left!=null){
	        if(traversal(node.left,count+=node.left.val,targetSum)){
                return true;
            }
            //回溯
            count-=node.left.val;
        }

        if(node.right!=null){
	        if(traversal(node.right,count+=node.right.val,targetSum)){
                return true;
            }
            //回溯
            count-=node.right.val;
        }
        return false;
    }
}

14.路径总和 ||

14.1问题

给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和 的路径

叶子节点 是指没有子节点的节点。

  • 示例一:

img

输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出:[[5,4,11,2],[5,8,4,5]]

14.2解法一:递归

14.2.1递归思路

(1)确定递归函数参数以及返回值
  • 参数说明:
    • 求根节点到 node 节点的路径之和 == targetSum
    • paths存放当前路径
    • res存放符合路径总和为targetSum的路径
    • count代表从根节点到该节点的路径中和
  • 无返回值
private void traversal(TreeNode node, List<Integer> paths, List<List<Integer>> res, int count, int targetSum)
(2)确定终止条件
  • 若该节点为叶子节点,则判断count==targetSum,符合则添加该paths到res中,否则返回
if(node.left==null && node.right==null){
	if(count==targetSum)    {
        res.add(new ArrayList<>(path));
    }
    return;
}
(3)确定递归逻辑
if(node.left!=null){
    paths.add(node.left.val);
	traversal(node.left,paths,res,count+=node.left.val,targetSum);
    //回溯
    paths.remove(paths.size()-1);
    count-=node.left.val;
}

if(node.right!=null){
    paths.add(node.right.val);
	traversal(node.right,paths,res,count+=node.right.val,targetSum);
    //回溯
    paths.remove(paths.size()-1);
    count-=node.right.val;
}

14.2.2代码实现

public List<List<Integer>> pathSum(TreeNode root, int targetSum) {

        int count=0;
        List<List<Integer>> res=new ArrayList<>();
        List<Integer> paths=new ArrayList<>();
        if(root==null){
            return res;
        }
        paths.add(root.val);
        traversal(root,paths,res,count+=root.val,targetSum);
        return res;
    }

    private void traversal(TreeNode node, List<Integer> paths, List<List<Integer>> res, int count, int targetSum){
        if(node.left==null && node.right==null){
	        if(count==targetSum){
                res.add(new ArrayList<>(paths));
            }
            return;
        }

        if(node.left!=null){
            paths.add(node.left.val);
	        traversal(node.left,paths,res,count+=node.left.val,targetSum);
            //回溯
            paths.remove(paths.size()-1);
            count-=node.left.val;
        }

        if(node.right!=null){
            paths.add(node.right.val);
	        traversal(node.right,paths,res,count+=node.right.val,targetSum);
            //回溯
            paths.remove(paths.size()-1);
            count-=node.right.val;
        }


    }
}

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

CRM集成:解锁业务增长与客户关系管理的关键

预计从2021年至2028年&#xff0c;CRM领域的市场规模将大幅跃升&#xff0c;从约580亿美元增长至1290亿美元。这一显著的增长并非偶然&#xff0c;而是源于CRM平台为企业带来的巨大价值。客户关系管理平台助力销售高效开发潜在客户&#xff0c;客户成功经理有效支持客户&#x…

VRRP+MSTP+BFD

一、组网 二、要求 PC6&#xff08;vlan 10内PC&#xff09;访问1.1.1.1走JR-1——CORE1——MSR到1.1.1.1 PC7&#xff08;vlan 20内PC&#xff09;访问1.1.1.1走JR-2——CORE2——MSR到1.1.1.1 链路故障时切换路线&#xff0c;来回路径一致 三、配置步骤 SR bfd echo-sou…

30.WEB渗透测试-数据传输与加解密(4)

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 内容参考于&#xff1a; 易锦网校会员专享课 上一个内容&#xff1a;29.WEB渗透测试-数据传输与加解密&#xff08;3&#xff09;-CSDN博客 加解密需要用到的源…

磁盘管理与文件管理

文章目录 一、磁盘结构二、MBR与磁盘分区分区的优势与缺点分区的方式文件系统分区工具挂载与解挂载 一、磁盘结构 1.硬盘结构 硬盘分类&#xff1a; 1.机械硬盘&#xff1a;靠磁头转动找数据 慢 便宜 2.固态硬盘&#xff1a;靠芯片去找数据 快 贵 硬盘的数据结构&#xff1a;…

InternVideo2重塑视频理解新标杆,多模态学习引领行业风向

引言&#xff1a;视频理解的新篇章——InternVideo2的介绍 随着视频内容在日常生活中的普及&#xff0c;视频理解技术的重要性日益凸显。视频不仅包含丰富的视觉信息&#xff0c;还蕴含着动态变化和多模态元素&#xff0c;如音频和文本。这些特性使得视频成为一个复杂的数据类型…

蓝桥杯-求阶乘

问题描述 满足 N!的末尾恰好有 区 个o的最小的 N 是多少? 如果这样的 N 不存在输出 -1。 输入格式 一个整数 区。 输出格式 一个整数代表答案。 样例输入 样例输出 10 评测用例规模与约定 对于 30% 的数据,1<K<106 对于 100% 的数据,1<K<1018 运行限制 最大运行时…

Leetcode算法训练日记 | day14

一、二叉树的前序遍历 1.题目 Leetcode&#xff1a;第 144 题 给你二叉树的根节点 root &#xff0c;返回它节点值的 前序 遍历。 示例 1&#xff1a; 输入&#xff1a;root [1,null,2,3] 输出&#xff1a;[1,2,3]示例 2&#xff1a; 输入&#xff1a;root [] 输出&#…

wps可以打钩的框框

方法一&#xff1a; 输入2611&#xff0c;按下altx 方法二&#xff1a; R 选中后->开始->字体wingdings字体

MATLAB 点云体素滤波 (58)

MATLAB 体素滤波 (58) 一、基本原理二、算法实现1.代码数据的海量性始终是点云处理时需要面临的一个大问题,严重的时间消耗和内存占用影响了点云处理的发展,当然了,点云数量主要应该看项目的实际需求,若是对细节要求较高,那么点云数量不可过少,但是要求过低时,我们就可…

番外篇 | YOLOv8改进之引入YOLOv9的ADown模块 | 替换YOLOv8卷积

前言:Hello大家好,我是小哥谈。YOLOv9是一种目标检测算法,而ADown模块是YOLOv9中的一个重要组成部分。ADown模块主要用于特征提取和下采样操作,以便在后续的检测任务中更好地捕捉目标的特征。具体来说,ADown模块是YOLOv9中的一个卷积块,由一系列卷积层和池化层组成。它的…

Linux网卡:连接虚拟与现实的桥梁

在介绍Linux网卡之前&#xff0c;让我们先迈入时光机&#x1f570;️&#xff0c;回到1980年代末期&#xff0c;互联网正在逐步从一个科研网络向公众网络转变&#xff0c;Linux——一个自由和开源的操作系统诞生了&#x1f427;。Linux的出现&#xff0c;对于计算机科学领域来说…

B端:发起个申请,审批慢如蜗牛,那是你不懂高效审批流程设计。

有时候我们发起个申请&#xff0c;让领导和上级审批&#xff0c;迟迟不见动静&#xff0c;又不好一直催促领导&#xff0c;或者领导不会操作&#xff0c;误操作&#xff0c;怎么办&#xff0c;其实你是缺乏高效的流程设计。 设计一个高效的审批流程对于B端系统非常重要&#x…

Unity核心学习

目录 认识模型的制作流程模型的制作过程 2D相关图片导入设置图片导入概述纹理类型设置纹理形状设置纹理高级设置纹理平铺拉伸设置纹理平台打包相关设置 SpriteSprite Editor——Single图片编辑Sprite Editor——Multiple图片编辑Sprite Editor——Polygon图片编辑SpriteRendere…

高精度地图导航论文汇总

文章目录 2022基于高精度地图的智能车辆路径规划与跟踪控制研究[M] 2023一种无人驾驶融合决策方案的设计与实现[M] 2022 基于高精度地图的智能车辆路径规划与跟踪控制研究[M] 摘要&#xff1a; 随着计算机及通信技术的不断进步&#xff0c;汽车行业也得到了飞速的发展。汽车在…

ZStack Cloud 5.0.0正式发布——Vhost主存储、隔离PVLAN网络、云平台报警优化、灰度升级增强四大亮点简析

近日&#xff0c;ZStack Cloud 5.0.0正式发布&#xff0c;推出了包含Vhost主存储、隔离PVLAN网络、云平台报警优化、灰度升级增强在内的一系列重要功能。云主机管理、物理机运维、密评合规、灾备服务等诸多使用场景和功能模块均有更新&#xff0c;为您带来更完善的平台服务、更…

机器人坐标系转换从局部坐标系转换到世界坐标系

矩阵方式&#xff1a; 下面是代码&#xff1a; #include <Eigen/Dense>static void transLocalToWorldCloudWith2dPose(const PointCloud &pc_tar, const QPose3f &pose, PointCloud &pc_org) {if (pc_tar.empty())return;PointCloud tmp_pc;Eigen::Rotati…

解读POP3:电子邮件查看必备技巧揭秘

在您点击阅读时&#xff0c;是否曾想过您是如何如此轻松地查看电子邮件的&#xff1f;对我们来说&#xff0c;这听起来可能只是几秒钟的加载时间&#xff0c;但实际上幕后发生了许多事情。邮局协议&#xff08;POP3&#xff09;是一种应用层协议&#xff0c;电子邮件客户端使用…

基于Android的记单词App系统的设计与实现

博主介绍&#xff1a;✌IT徐师兄、7年大厂程序员经历。全网粉丝15W、csdn博客专家、掘金/华为云//InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;&#x1f3…

Linkedin领英封号原因是什么?如何养号?

领英作为全球最大的职场社交平台&#xff0c;用户总数已超过8亿&#xff0c;覆盖200多个国家和地区&#xff0c;中国会员总数也已经累计超过5700万&#xff0c;庞大的基数使得他迅速成为跨境业务员建立形象&#xff0c;拓展人脉&#xff0c;开发客户的重要渠道。“领英职场”的…

C语言面试题之检查二叉树平衡性

检查二叉树平衡性 实例要求 1、实现一个函数&#xff0c;检查二叉树是否平衡&#xff1b;2、在这个问题中&#xff0c;平衡树的定义如下&#xff1a;任意一个节点&#xff0c;其两棵子树的高度差不超过 1&#xff1b; 示例 1: 给定二叉树 [3,9,20,null,null,15,7]3/ \9 20/…