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实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Android实现两台手机屏幕共享和远程控制功能

《Android实现两台手机屏幕共享和远程控制功能》在远程协助、在线教学、技术支持等多种场景下,实时获得另一部移动设备的屏幕画面,并对其进行操作,具有极高的应用价值,本项目旨在实现两台Android手... 目录一、项目概述二、相关知识2.1 MediaProjection API2.2 Socket 网络

Java中的JSONObject详解

《Java中的JSONObject详解》:本文主要介绍Java中的JSONObject详解,需要的朋友可以参考下... Java中的jsONObject详解一、引言在Java开发中,处理JSON数据是一种常见的需求。JSONObject是处理JSON对象的一个非常有用的类,它提供了一系列的API来操作J

使用Python实现图像LBP特征提取的操作方法

《使用Python实现图像LBP特征提取的操作方法》LBP特征叫做局部二值模式,常用于纹理特征提取,并在纹理分类中具有较强的区分能力,本文给大家介绍了如何使用Python实现图像LBP特征提取的操作方... 目录一、LBP特征介绍二、LBP特征描述三、一些改进版本的LBP1.圆形LBP算子2.旋转不变的LB

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

SpringBoot多数据源配置完整指南

《SpringBoot多数据源配置完整指南》在复杂的企业应用中,经常需要连接多个数据库,SpringBoot提供了灵活的多数据源配置方式,以下是详细的实现方案,需要的朋友可以参考下... 目录一、基础多数据源配置1. 添加依赖2. 配置多个数据源3. 配置数据源Bean二、JPA多数据源配置1. 配置主数据

C# Where 泛型约束的实现

《C#Where泛型约束的实现》本文主要介绍了C#Where泛型约束的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录使用的对象约束分类where T : structwhere T : classwhere T : ne

将Java程序打包成EXE文件的实现方式

《将Java程序打包成EXE文件的实现方式》:本文主要介绍将Java程序打包成EXE文件的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录如何将Java程序编程打包成EXE文件1.准备Java程序2.生成JAR包3.选择并安装打包工具4.配置Launch4

SpringBoot内嵌Tomcat临时目录问题及解决

《SpringBoot内嵌Tomcat临时目录问题及解决》:本文主要介绍SpringBoot内嵌Tomcat临时目录问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录SprinjavascriptgBoot内嵌Tomcat临时目录问题1.背景2.方案3.代码中配置t

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr