当前位置:网站首页>LeetCode 练习——113. 路径总和 II
LeetCode 练习——113. 路径总和 II
2022-07-07 07:29:00 【SK_Jaco】
1.题目描述
113. 路径总和 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
输出:[]
2.解题思路与代码
2.1 解题思路
这道题求从根节点到叶节点的上和为目标的路径,可以使用前序遍历进行处理。当节点不为叶节点时,将当前节点放入路径列表中,并且目标值减去当前节点值;如果当前节点是叶节点时,就需要判断 target 是否为 0,如果是0,那么就把当前路径放入结果列表中;如果不是0,则返回。在处理完左节点和右节点之后需要将当前节点从路径列表中删除。以题目示例 1 为例进行图解:
首先从根节点开始向下遍历二叉树,将当前节点放入路径列表中,同时 target 减去当前节点值。
当遍历到叶节点时,判断 target 是否为 0,此时不为 0,因此这条路径不满足要求,返回上一节点。
返回同时需要将当前节点从路径列表中移除,然后继续向下到 2 这个节点。此时 target 等于 0,满足要求,将 [5, 4, 11, 2] 这条路径放入结果中。重复上面步骤继续遍历知道结束为止。
2.2 代码
class Solution {
List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int target) {
if (root == null) {
return ans;
}
process(root, new ArrayList<>(), target);
return ans;
}
public void process(TreeNode root, List<Integer> tmp, int target) {
if (root == null) {
return;
}
tmp.add(root.val);
target -= root.val;
if (root.left == null && root.right == null && target == 0){
// 如过当前节点为叶节点,并且 target 等于 0,将路径放入结果列表
ans.add(new ArrayList<>(tmp));
}
process(root.left, tmp, target);
process(root.right, tmp, target);
// 处理完左右节点之后将当前节点从路径列表中移除
tmp.remove(tmp.size() - 1);
}
}
2.3 测试结果
通过测试
3.总结
- 使用前序遍历进行解答
- 每个节点在处理完左右节点后需要将当前节点移出路径列表
边栏推荐
- Selenium+bs4 parsing +mysql capturing BiliBili Tarot data
- Finally, there is no need to change a line of code! Shardingsphere native driver comes out
- Guys, have you ever encountered the case of losing data when Flink CDC reads mysqlbinlog? Every time the task restarts, there is a probability of losing data
- 企业实战|复杂业务关系下的银行业运维指标体系建设
- 洛谷P2482 [SDOI2010]猪国杀
- Basic use of JMeter to proficiency (I) creation and testing of the first task thread from installation
- Three years after graduation
- 2020 Zhejiang Provincial Games
- [untitled]
- C socke server, client, UDP
猜你喜欢
能源路由器入门必读:面向能源互联网的架构和功能
The applet realizes multi-level page switching back and forth, and supports sliding and clicking operations
ORM--查询类型,关联查询
Postman interface test I
Web3.0 series distributed storage IPFs
[original] what is the core of programmer team management?
Bean operation domain and life cycle
Natapp intranet penetration
基础篇:带你从头到尾玩转注解
The new activity of "the arrival of twelve constellations and goddesses" was launched
随机推荐
Introduction to energy Router: Architecture and functions for energy Internet
Basic use of JMeter to proficiency (I) creation and testing of the first task thread from installation
Some thoughts on the testing work in the process of R & D
Integer inversion
Web3.0 series distributed storage IPFs
flink. CDC sqlserver. You can write the DEM without connector in sqlserver again
Before joining the chain home, I made a competitive product analysis for myself
一大波开源小抄来袭
Gym - 102219J Kitchen Plates(暴力或拓扑序列)
Introduction to automated testing framework
Basic chapter: take you through notes
使用BigDecimal的坑
C# 初始化程序时查看初始化到哪里了示例
Sword finger offer II 107 Distance in matrix
Parameter sniffing (1/2)
一文讲解单片机、ARM、MUC、DSP、FPGA、嵌入式错综复杂的关系
C socke server, client, UDP
Postman interface test I
The physical meaning of imaginary number J
Applet sliding, clicking and switching simple UI