图解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^)/ ~ 「干货分享，每天更新」