路径总和-112

news/2024/10/5 23:48:01

题目描述

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

解题思路

我们这题采用任何一种遍历方式都是可以的,这题同样是有回溯的思想,如果不太懂的话可以去看看前面《求二叉树的左右路径》这一题,我们先去遍历左子树,遍历的时候如果节点的左右子树都为空说明我们已经到了叶子节点,此时我们就可以做判断了,看看是不是和我们的targetSum一致,如果不一致则它的父节点会产生回溯去遍历父节点的另一个子树,同样再去看看是否和targetSum是否一致,如果一致就可以直接填写结果,不一致则继续由它们的父节点回溯去判断另一颗子树。

代码实例

class Solution {public boolean judge = false;public boolean hasPathSum(TreeNode root, int targetSum) {List<Integer> list = new ArrayList<>();if(root==null){return false;}else{list.add(root.val);bianli(root, targetSum, list);return judge;}}public void bianli(TreeNode root, int targetSum, List<Integer> list) {if (root.left == null && root.right == null) {if (sum(list) == targetSum) {judge = true;return;}}if (root.left != null) {list.add(root.left.val);bianli(root.left, targetSum, list);list.remove(list.size() - 1);}if (root.right != null) {list.add(root.right.val);bianli(root.right, targetSum, list);list.remove(list.size() - 1);}}public int sum(List<Integer> list) {int sum = 0;for (Integer in : list) {sum += in;}return sum;}}

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

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

相关文章

小林coding学习笔记(进程调度算法)

//进程调度算法 进程调度算法是CPU通过进程调度算法决定某个时刻去调用哪个进程到CPU上运行的算法 1、先来先服务调度算法 每次从就绪队列的队头调度到CPU上运行,直到进程退出或被阻塞,才会继续从队列中调度进程运行。 特点:对短作业不利,对长作业有利,无法平衡短作业与长…

spring mvc详细讲解(前后端分离模式)

在前后端分离模式下,Spring MVC 的作用主要集中在处理后端的业务逻辑和 API 接口,而不再直接管理视图部分。也就是说,Spring MVC 的重点是如何处理客户端的请求并返回数据(通常以 JSON 或 XML 格式),而视图渲染交给前端框架(如 Vue.js、React 等)来完成。 下面是针对前…

关于API淘宝数据接口

在当今数字化商业时代,淘宝作为全球领先的电商平台,提供了丰富的API接口,使开发者能够高效地获取和管理电商数据。淘宝API接口不仅简化了与淘宝平台的交互,还为商家提供了强大的数据支持,帮助他们更好地分析市场趋势、优化店铺运营、提升用户体验。 淘宝API接口概述 淘宝A…

解决 Debian下 nvm ls-remote 列表只出现iojs版本的问题

1.进入 .bashrc 里vi ~/.bashrc2. o键新开一行增加下面内容export NVM_NODEJS_ORG_MIRROR=https://nodejs.org/dist 3.重载nvm配置source ~/.bashrc4.验证配置是否修改成功,如图则表示成功echo $NVM_NODEJS_ORG_MIRROR 5.再次查看可安装的node版本nvm ls-remote 备注:如果上…

Arrays类的使用

1.Arrays 在IDEA中有一个叫Arrays的类,它可以执行数组的一系列操作 2.Arrays.toString 该代码用于执行数组的打印,因为数组的打印用sout并不能输出出来(数组面向于对象),所以得用该代码输出3.Arrays.sort 将数组的数字从小到大排序4.Arrays.fill 将数组中的数字用其他数字…

跨界融合,GIS如何赋能游戏商业——以《黑神话:悟空》为例

在数字化时代,地理信息系统(GIS)技术正以其独特的空间分析和可视化能力,为游戏产业带来革命性的变革。《黑神话:悟空》作为中国首款3A级别的动作角色扮演游戏,不仅在游戏设计和技术上取得了突破,更在商业模式上展现了跨界融合的新路径。 1. GIS技术在游戏设计中的应用《…

如何在windows中设置系统代理

1、部署Gemini Gemini使用教程 - 迅捷网络[来送福利] - 博客园 (cnblogs.com) 2.左下角搜索设置或直接搜索代理 3.Gemini后台复制需要访问的那个设备IP 4.windows上设置代理 5.使用提示 1.不用的时候清取消此代理,避免你的网络都走此代理; 2.要走你本地电脑的网络的话,可以加…

常回家看看之house_of_cat

house_of_cat 前言: house of cat 这个利用手法和前面提到的 house of kiwi ,和 house of emma 利用的手法是一个链子,当程序无法通过main函数返回时候,或者程序不能显性调用exit函数的时候,我们可以通过 __malloc_assert 来刷新IO流,当然这个函数在2.35之后移除了刷新IO…