图解LeetCode——剑指 Offer 34. 二叉树中和为某一值的路径

简介: 图解LeetCode——剑指 Offer 34. 二叉树中和为某一值的路径

一、题目

给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。叶子节点 是指没有子节点的节点。

二、示例

2.1> 示例 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.2> 示例 2:

【输入】root = [1,2,3], targetSum = 5

【输出】[]

2.3> 示例 3:

【输入】root = [1,2], targetSum = 0

【输出】[]

提示:

  • 树中节点总数在范围 [0, 5000]
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

三、解题思路

  • 根据题目要求,我们需要寻找N条从根路径到叶子节点的路径,并要求满足该路径节点之和等于targetSum;既然涉及到二叉树节点遍历,常用的就是深度优先算法广度优先算法,那么由于本题涉及从根路径到叶子节点的路径,那么我们可以采用深度优先算法+ 前序遍历对这道题进行解答。
  • 其实本题的一个难点就是如何去拼装最终结果List<List<Integer>> result,那么既然是需要获得满足条件的路径节点值的集合,我们就可以创建一个变量LinkedList<Integer> path,用于记录当前所经过的节点值。那么当我们从根节点遍历到叶子节点之后,会有如下两种情况:

情况1】所有节点总和正好等于targetSum,那么我们通过复制path,然后保存到result中即可。如果还有其他树节点需要遍历,逐一回溯path末尾节点val值。

情况2】所有节点总和不等于targetSum,如果还有其他树节点需要遍历,逐一回溯path末尾节点val值。

  • 需要注意的是,当我们确认某一条路径等于targetSum之后,我们需要“复制”该路径(即:通过new LinkedList(path);)否则路径就会随着回溯操作而发生变化了。上面就是具体的解题思路,下面我们还是以输入:root = [5,4,8,11,null,13,4,7,2,null,null,5], targetSum = 22为例,看一下具体的操作过程是怎么样的。请见下图所示:

四、代码实现

classSolution {
List<List<Integer>>result;
LinkedList<Integer>path;
publicList<List<Integer>>pathSum(TreeNoderoot, inttarget) {
result=newLinkedList();
path=newLinkedList();
dfs(root, target);
returnresult;
    }
publicvoiddfs(TreeNodenode, intvalue) {
if (node==null) return;
path.addLast(node.val);
if (node.val==value&&node.left==null&&node.right==null) 
result.add(newLinkedList(path));
dfs(node.left, value-node.val);
dfs(node.right, value-node.val);
path.removeLast(); // 回溯    }
}


今天的文章内容就这些了:

写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享

更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享,每天更新」

相关文章
|
21天前
【LeetCode 35】112.路径总和
【LeetCode 35】112.路径总和
21 0
|
21天前
【LeetCode 36】113.路径总和II
【LeetCode 36】113.路径总和II
26 0
|
21天前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
11 0
|
21天前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
10 0
|
21天前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
10 0
|
21天前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
11 0
|
21天前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
12 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
52 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
102 2