力扣112,路径总和

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

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

示例 1:

输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出:true
解释:等于目标和的根节点到叶节点路径如上图所示。
/**
 * 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 hasPathSum(TreeNode root, int targetSum) {
        // 如果根节点为空,则返回false
        if (root == null) return false;
        
        // 如果当前节点是叶子节点,且节点值等于目标和,则返回true
        if (root.left == null && root.right == null && targetSum == root.val) {
            return true;
        }
        
        // 递归检查左子树
        boolean leftPathSum = false;
        if (root.left != null) {
            leftPathSum = hasPathSum(root.left, targetSum - root.val);
        }
        
        // 递归检查右子树
        boolean rightPathSum = false;
        if (root.right != null) {
            rightPathSum = hasPathSum(root.right, targetSum - root.val);
        }
        
        // 返回左右子树的结果
        return leftPathSum || rightPathSum;
    }
}

回溯更好的展现出来 

/**
 * 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 tral(TreeNode root,int count){
        if(root==null) return false;
        if(root.left==null&&root.right==null&&count==0) return true;
        if(root.left!=null){
            count-=root.left.val;
            if(tral(root.left,count)) return true;
            count+=root.left.val;//回溯
        }
         if(root.right!=null){
            count-=root.right.val;
            if(tral(root.right,count)) return true;
            count+=root.right.val;//回溯
        }
        return false;
    }
    
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null) return false;
        return tral(root,targetSum-root.val);
    }
}

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

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

示例 1:

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

提示:

  • 树中节点总数在范围 [0, 5000] 内
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000
/**
 * 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 void travelsal(TreeNode root,int count,List<List<Integer>> result,List<Integer> path){
        if(root==null) return;
        path.add(root.val);//这里将遍历的节点值添加到path中
        if(root.left == null&&root.right==null&&count-root.val==0) result.add(new ArrayList<>(path));
        if(root.left!=null){
            //这里就不用add了
            travelsal(root.left,count-root.val,result,path);
        }
        if(root.right!=null){
             //这里就不用add了
            travelsal(root.right,count-root.val,result,path);
        }
        path.remove(path.size()-1);//回溯,移除当前节点,恢复路径状态!!!!!!
    }
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        if(root==null) return result;
        List<Integer> path = new ArrayList<>();
         travelsal(root,targetSum,result,path);
        return result;
    }
}

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

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

相关文章

.cur 鼠标光标编辑器

详解透明贴图和三元光栅操作 - CodeBus 鼠标指针文件格式解析——Windows&#xff08;二&#xff09; (qq.com) [C/C] RGBA数组生成Windows下的ico文件_c ico格式-CSDN博客 色环设计 - CodeBus 左键绘制 右键选颜色 ctrl右键设置鼠标热点 F1导出.cur文件 //代码来源&…

分组查询得到一列多行数据后,怎么用来和表中的某列数据进行一一比较

#10&#xff09;查询每个学生超过他自己选修课程平均成绩的课程号 这里要先进行分组得到每个学号对应的平均成绩&#xff0c;在用表中的成绩grade与得到的平均成绩一一比较 这里可以进行连表操作&#xff0c;把分组查询得到的结果与原表通过sno学号进行等值连接 &#xff0c;就…

轻量级SQLite可视化工具Sqliteviz

什么是 Sqliteviz &#xff1f; Sqliteviz 是一个单页面离线优先的渐进式网络应用&#xff08;PWA&#xff09;&#xff0c;用于完全客户端的 SQLite 数据库或 CSV 文件的可视化。 所谓完全客户端&#xff0c;就是您的数据库永远不会离开您的计算机。使用 sqliteviz&#xff0c…

ubuntu server 安装emqx tdengine

文章目录 1 安装emqx2 安装taos 1 安装emqx 86 wget https://www.emqx.com/zh/downloads/broker/5.6.0/emqx-5.6.0-ubuntu22.04-amd64.deb87 ls88 pwd89 sudo apt install ./emqx-5.6.0-ubuntu22.04-amd64.deb90 sudo systemctl start emqx91 systemctl status emqx92 s…

C语言求自幂数(水仙花数与其他自幂数)

前言 今天我们来看一下如果求解自幂数&#xff08;水仙花数&#xff09;&#xff0c;水仙花数是自幂数的一种&#xff0c;我们来看看自幂数的概念吧&#xff0c;当一个n位数&#xff0c;它的每个位上的数字的n次幂之和等于它本身的时候&#xff0c;我们称这个数为自幂数。水仙花…

文本溢出体验进阶:CSS 技巧实现单行/多行隐藏展示以及实际场景应用,确保内容可读性和布局整洁性

CSS文本溢出隐藏是一种常见的场景&#xff0c;它广泛应用于各种网页设计中&#xff0c;旨在确保内容的可读性和布局的整洁性&#xff0c;特别是在空间有限或需要适应不同屏幕尺寸的情况下。 一、文本溢出隐藏并显示省略号 1、单行文本溢出隐藏并显示省略号 对于单行文本&…

怎么找程序员对象?和程序员谈恋爱是什么体验?

和程序员谈恋爱是一种非常累的体验&#xff0c;因为他们大部分时间都会加班&#xff0c;守在电脑面前不能够陪自己。但是这样的男孩子&#xff0c;忠诚、认真、不会花花草草、收入贼高&#xff0c;恋爱幸福指数接近满分哦&#xff01; 程序员都是宅男&#xff0c;都是电脑狂魔&…

中科院JCR期刊分区介绍

文章目录 1. 背景2. 简介3. 学科分类方法4. 分区表计算方法5. 分区指标说明5.1 IF5.2 3年平均IF5.3 CI 6. 中科院分区和JCR期刊分区有哪些异同&#xff1f;6.1 数据基础相同6.2 学科划分小类部分相同 1. 背景 SCI作为论文与引文分析的重要手段, 被国内各级科研管理部门所重视,…

stm32开发之threadx之modulex模块文件的生成脚本项目

前言 为了保证在window上运行&#xff0c;且体积小的问题&#xff0c;所以采用c语言编写生成脚本,将相关路径由json文件进行配置,使用了一个cjson库进行解析项目构建使用的是cmake 项目代码 CMakeLists文件 cmake_minimum_required(VERSION 3.27) project(txm_bat_script C…

stm32开发之threadx+modulex+filex+shell组件(实现命令行动态加载程序)

前言 前几篇博客基本上已经将filex、levelx、threadx、modulex、shell 组件大概都记录了一遍.本篇博客做个综合实际案例记录. 实现效果 代码程序 Modulex组件 源文件 /** Copyright (c) 2024-2024&#xff0c;shchl** SPDX-License-Identifier: Apache-2.0** Change Logs:…

easyx库的学习(文字绘制)

前言 昨天刚刚写完了基本图形的制作&#xff0c;今天直接可以来看看&#xff0c;在easyx中使用文字 直接看代码吧 文字绘制 void drawTest() {printf("hello,EasyX");//指的是在控制台打印//设置字体大小&#xff0c;样式settextstyle(30, 0, "微软雅黑&quo…

4.4 @ControllerAdvice全局数据处理

4.4 ControllerAdvice全局数据处理 1. 全局异常处理 &#xff20;ExceptionHandler2. 添加全局数据 ModelAttribute3. 请求参数预处理 InitBinder 顾名思义&#xff0c;&#xff20;ControllerAdvice 就是&#xff20;Controller 增强版。&#xff20;ControllerAdvice 主要用来…

【LAMMPS学习】八、基础知识(3.8)计算扩散系数

8. 基础知识 此部分描述了如何使用 LAMMPS 为用户和开发人员执行各种任务。术语表页面还列出了 MD 术语&#xff0c;以及相应 LAMMPS 手册页的链接。 LAMMPS 源代码分发的 examples 目录中包含的示例输入脚本以及示例脚本页面上突出显示的示例输入脚本还展示了如何设置和运行各…

esp32-通过wifi使用timelib库同步时间(三)

库的安装 本文基于platformIO&#xff0c;安装较为简单如下图 实例代码 完整代码如下&#xff0c;如果时间获取超时请使用time1.aliyun.com获取时间。 /** Time_NTP.pde* Example showing time sync to NTP time source** This sketch uses the Ethernet library*/#include …

通过实例学C#之序列化与反序列化XmlSerializer类

简介 可以将类序列化成xml文件&#xff0c;或者将xml文件反序列化成类对象&#xff0c;一般用于保存或加载项目参数。 构造函数 XmlSerializer() 不使用函数创建一个xmlSerializer对象。 XmlSerializer(Type type) 使用type对象创建一个xmlSerializer对象&#xff0c;注意&…

NotePad++联动ABAQUS

Abaqus 中脚本运行 1. 命令区kernel Command Line Interface &#xff08;KCLI&#xff09; execfile(C:\\temp\second develop\chapter2\pyTest1.py)2. CAE-Run Script File->Run Script 3. Abaqus command Abaqus cae noGUIscript.py(前后处理都可)Abaqus Python scr…

牛x之路 - Day1

Day1 微积分之屠龙宝刀&#xff08;武林秘籍&#xff09; 之前的一些东西都在pdf上记得笔记&#xff0c; 没有在这个上面展示一遍&#xff0c;只好学到相关内容的时候再提叙啦&#xff1b;所以其实再写这个小记的时候&#xff0c;我已经看了一半的书&#xff0c;但是不要紧&am…

【结构型模式】组合模式

一、组合模式概述 组合模式的定义与意图&#xff1a;将对象组合成树形结构来表现“整体/部分”层次结构。组合能让客户以一致的方式处理个别对象以及对象组合。&#xff08;对象结构型&#xff09; 组合模式分析&#xff1a; 1.当容器对象的某一个方法被调用时&#xff0c;将遍…

OpenHarmony网络协议通信—kcp

kcp 是一种 ARQ 协议,可解决在网络拥堵情况下 tcp 协议的网络速度慢的问题 下载安装 直接在 OpenHarmony-SIG 仓中搜索 kcp 并下载。 使用说明 准备一套完整的 OpenHarmony 3.1 Beta 代码 库代码存放路径&#xff1a;./third_party/kcp 修改添加依赖的编译脚本 在/develo…

书生·浦语实战营第二期(六)——Agent

一、概述&#xff1a; 1.1、Lagent: Lagent 是一个轻量级开源智能体框架&#xff0c;旨在让用户可以高效地构建基于大语言模型的智能体。同时它也提供了一些典型工具以增强大语言模型的能力。 Lagent 目前已经支持了包括 AutoGPT、ReAct 等在内的多个经典智能体范式&#xf…