一、题目
给你二叉树的根节点 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^)/ ~ 「干货分享,每天更新」