第113题:路径总和II
2024-08-27 10:47:00
一. 问题描述
给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树,以及目标和 sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
二. 解题思路
本题思路:采用深度优先遍历和递归的方式进行求解。
步骤一:构建递归函数(全局变量list存储结果值,局部变量data存储当前某一条路径,root当前节点,num当前路径值的和,tacket目标值)。
步骤二:递归函数进行判断:如果当前节点是叶子节点,且num==tacket,则将当前data添加到list中,否则将当前节点变成当前节点的左子树节点和右子树节点重复步骤二。
步骤三:当遍历完所有节点则放回输出list。
三. 执行结果
执行用时 :3 ms, 在所有 java 提交中击败了61.35%的用户
内存消耗 :40.7 MB, 在所有 java 提交中击败了34.70%的用户
四. Java代码
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> list=new ArrayList<List<Integer>>();
if(root==null) {
return list;
}else {
List<Integer> data=new ArrayList<Integer>();
data.add(root.val);
getTree(list,data,root,root.val,sum);
return list; }
}
public void getTree(List<List<Integer>> list,List<Integer> data,TreeNode root,int num,int tacket) { if(root.left==null&&root.right==null&&num==tacket) {
list.add(data);
} if(root.left!=null) {
List<Integer> temp=new ArrayList<Integer>(data);
temp.add(root.left.val);
getTree(list,temp,root.left,num+root.left.val,tacket); } if(root.right!=null) {
List<Integer> tempright=new ArrayList<Integer>(data);
tempright.add(root.right.val);
getTree(list,tempright,root.right,num+root.right.val,tacket);
} }
}
最新文章
- 简谈ashx
- mysql 之基本操作
- Windows下pry安装和配置
- Hadoop-Drill深度剖析
- 通过SEP禁用USB
- Data Flow ->;>; Merge
- C#面向对象基础01
- 崩溃信息:Message from debugger: Terminated due to signal 9
- 负载均衡集群中的session解决方案
- BIND9的架构与机制笔记1
- android面试题之四
- ValueStack背后的OGNL表达式
- IOS的UIPickerView 和UIDatePicker
- Github Page+Bmob实现简单动态功能
- 数据库中float类型字段,转化到前端显示,统一保留两位小数
- redis的持久化之RDB的配置和原理
- Django 上下文处理器
- linux php7 安装redis扩展
- vue中axios的封装
- android拾遗——四大基本组件介绍与生命周期