JAVA学习-练习试用Java实现“路径总和 II”

2024-08-24 14:28

本文主要是介绍JAVA学习-练习试用Java实现“路径总和 II”,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

问题:

给定二叉树的根节点 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]]
示例 2:

输入:root = [1,2,3], targetSum = 5
输出:[]
示例 3:

输入:root = [1,2], targetSum = 0
输出:[]
提示:

树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

解答思路:

以下是使用 Java 实现找出所有从根节点到叶子节点路径总和等于给定目标和的路径的代码:

import java.util.ArrayList;
import java.util.List;class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;}
}public class PathSumII {public static List<List<Integer>> pathSum(TreeNode root, int targetSum) {List<List<Integer>> result = new ArrayList<>();dfs(root, targetSum, new ArrayList<>(), result);return result;}private static void dfs(TreeNode root, int targetSum, List<Integer> path, List<List<Integer>> result) {if (root == null) {return;}path.add(root.val);if (root.left == null && root.right == null && targetSum == root.val) {result.add(new ArrayList<>(path));}dfs(root.left, targetSum - root.val, path, result);dfs(root.right, targetSum - root.val, path, result);path.remove(path.size() - 1);}public static void main(String[] args) {// 构建二叉树TreeNode root = new TreeNode(5);root.left = new TreeNode(4);root.right = new TreeNode(8);root.left.left = new TreeNode(11);root.left.left.left = new TreeNode(7);root.left.left.right = new TreeNode(2);root.right.left = new TreeNode(13);root.right.right = new TreeNode(4);root.right.right.left = new TreeNode(5);root.right.right.right = new TreeNode(1);int targetSum = 22;List<List<Integer>> paths = pathSum(root, targetSum);for (List<Integer> path : paths) {System.out.println(path);}}
}

上述代码中,我们首先定义了一个'TreeNode'类来表示二叉树的节点。然后,在'pathSum'方法中,我们使用深度优先搜索(DFS)的方式遍历二叉树。在每次递归中,我们将当前节点的值添加到路径中,并检查是否满足目标和。如果满足,我们将当前路径添加到结果列表中。然后,我们继续递归遍历左子树和右子树,并在回溯时将当前节点从路径中移除。

在'main'方法中,我们构建了一个示例二叉树,并指定了目标和。然后,我们调用'pathSum'方法获取所有满足条件的路径,并打印出来。

(文章为作者在学习java过程中的一些个人体会总结和借鉴,如有不当、错误的地方,请各位大佬批评指正,定当努力改正,如有侵权请联系作者删帖。)

这篇关于JAVA学习-练习试用Java实现“路径总和 II”的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1102734

相关文章

Java中StopWatch的使用示例详解

《Java中StopWatch的使用示例详解》stopWatch是org.springframework.util包下的一个工具类,使用它可直观的输出代码执行耗时,以及执行时间百分比,这篇文章主要介绍... 目录stopWatch 是org.springframework.util 包下的一个工具类,使用它

Java进行文件格式校验的方案详解

《Java进行文件格式校验的方案详解》这篇文章主要为大家详细介绍了Java中进行文件格式校验的相关方案,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、背景异常现象原因排查用户的无心之过二、解决方案Magandroidic Number判断主流检测库对比Tika的使用区分zip

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

springboot security使用jwt认证方式

《springbootsecurity使用jwt认证方式》:本文主要介绍springbootsecurity使用jwt认证方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录前言代码示例依赖定义mapper定义用户信息的实体beansecurity相关的类提供登录接口测试提供一

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4