网络异常，图片无法展示
|
「这是我参与2022首次更文挑战的第9天，活动详情查看：2022首次更文挑战」
给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。
示例:
给定如下二叉树，以及目标和 sum = 22，
5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 复制代码
返回:
3 解释： 和为 22 的路径有：[5,4,11,2], [5,8,4,5], [4,11,7] 复制代码
提示：
节点总数 <= 10000
解题思路
本题要求我们在二叉树中，找出路径上节点和值等于目标值的路径的数量。这里的路径的起点可以是任何一个节点，终点也可以是任何一个节点，但是路径必须是从上到下的。
所以我们可以以任何一个节点为起点，向下查找路径，并记录节点和值，当和值等于目标值的时候，就说明我们找到了一个符合条件的路径，记录数量。这里递归函数的退出条件就是当我们找到一个空节点为止。
当我们处理完了这样的一个过程，就找到了所有符合条件的路径，也就得到了符合条件的路径的数量。
代码实现
var pathSum = function(root, sum) { // 获取路径 传入节点和目标值 function getPath(node,target){ // 如果当前节点为空，递归结束，返回 0 // 因为空节点肯定是找不到等于目标值的路径的 if(node===null) return 0; // 初始化数量为0，并记录当前节点值 let num = 0,nodeVal = node.val // 如果当前节点值等于目标值，数量+1 if(nodeVal === target) num++ // 获取后续的目标值 const val = target-nodeVal // 递归处理左子树 num += getPath(node.left,val) // 递归处理右子树 num += getPath(node.right,val) // 如果左子树不为空并且左子树没有被作为起点进行过查找 // 以左子树为起点查找路径 if(node.left&&!node.left.tag){ // 给左子树打上标记，证明作为起点使用过 node.left.tag = true; num += getPath(node.left,sum) } // 如果右子树不为空并且右子树没有被作为起点进行过查找 // 以右子树为起点查找路径 if(node.right&&!node.right.tag){ // 给右子树打上标记，证明作为起点使用过 node.right.tag = true; num += getPath(node.right,sum) } // 返回符合条件的路径的数量 return num; } // 返回结果值 return getPath(root,sum) }; 复制代码
这里要注意的是，因为递归过程中，有的节点会被经过多次，所以要记录当前节点是否被当做起点进行过查找，防止重复查找。
至此我们就完成了 leetcode-面试题 04.12-求和路径
如有任何问题或建议，欢迎留言讨论！👏🏻👏🏻👏🏻
