当前位置:网站首页>Leetcode exercise - 113 Path sum II
Leetcode exercise - 113 Path sum II
2022-07-07 10:11:00 【SK_ Jaco】
1. Title Description
113. The sum of the paths II
Give you the root node of the binary tree root And an integer target and targetSum , Find out all From the root node to the leaf node The path sum is equal to the given target sum .
Leaf node A node without children .
Example 1:
Input :root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output :[[5,4,11,2],[5,8,4,5]]
Example 2:
Input :root = [1,2,3], targetSum = 5
Output :[]
Example 3:
Input :root = [1,2], targetSum = 0
Output :[]
2. Problem solving ideas and codes
2.1 Their thinking
This problem is to find the path from the root node to the upper sum of the leaf node as the target , You can use preorder traversal for processing . When the node is not a leaf node , Put the current node into the path list , And the target value minus the current node value ; If the current node is a leaf node , You need to judge target Is it 0, If it is 0, Then put the current path into the result list ; If not 0, Then return to . After processing the left and right nodes, you need to delete the current node from the path list . Take the topic as an example 1 As an example :
First, traverse the binary tree downward from the root node , Put the current node into the path list , meanwhile target Subtract the current node value .
When traversing the leaf node , Judge target Is it 0, Not at this time 0, Therefore, this path does not meet the requirements , Return to the previous node .
When returning, you need to remove the current node from the path list , Then continue down to 2 This node . here target be equal to 0, Meet the requirements , take [5, 4, 11, 2] This path is put into the result . Repeat the above steps and continue to traverse until the end .
2.2 Code
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){
// If the current node is a leaf node , also target be equal to 0, Put the path into the result list
ans.add(new ArrayList<>(tmp));
}
process(root.left, tmp, target);
process(root.right, tmp, target);
// After processing the left and right nodes, remove the current node from the path list
tmp.remove(tmp.size() - 1);
}
}
2.3 test result
Pass the test
3. summary
- Use preorder traversal to solve
- Each node needs to move the current node out of the path list after processing the left and right nodes
边栏推荐
- ORM模型--数据记录的创建操作,查询操作
- 内存==c语言1
- 学习记录——高精度加法和乘法
- 官媒关注!国内数字藏品平台百强榜发布,行业加速合规健康发展
- Before joining the chain home, I made a competitive product analysis for myself
- 终于可以一行代码也不用改了!ShardingSphere 原生驱动问世
- Can I open a stock trading account online? Is it safe
- 2020 Zhejiang Provincial Games
- Introduction to automated testing framework
- 大整数类实现阶乘
猜你喜欢
Bean 作⽤域和⽣命周期
Applet popup half angle mask layer
Future development blueprint of agriculture and animal husbandry -- vertical agriculture + artificial meat
ORM--查询类型,关联查询
一大波开源小抄来袭
arcgis操作:dwg数据转为shp数据
每周推荐短视频:L2级有哪些我们日常中经常会用到的功能?
ORM -- grouping query, aggregation query, query set queryset object properties
SolidWorks工程图中添加中心线和中心符号线的办法
Bean operation domain and life cycle
随机推荐
单片机(MCU)最强科普(万字总结,值得收藏)
14th test
Hcip first day notes sorting
web3.0系列之分布式存储IPFS
ORM -- grouping query, aggregation query, query set queryset object properties
Phpcms realizes PC website access to wechat native payment
ArcGIS operation: batch modify attribute table
The method of word automatically generating directory
Main (argc, *argv[]) details
Introduction to uboot
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
Internship log - day07
UnityWebRequest基础使用之下载文本、图片、AB包
CDZSC_ 2022 winter vacation personal training match level 21 (1)
phpcms实现PC网站接入微信Native支付
位操作==c语言2
Analyze Android event distribution mechanism according to popular interview questions (I)
Use of JSON extractor originals in JMeter
The physical meaning of imaginary number J
SQLyog数据库怎么取消自动保存更改