北京优化网站建设,帮人家做网站,长春网站如何制作,你有网站 我做房东 只收佣金的网站题目
给定一个二叉树的根节点 root #xff0c;和一个整数 targetSum #xff0c;求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始#xff0c;也不需要在叶子节点结束#xff0c;但是路径方向必须是向下的#xff08;只能从父节点到子节…题目
给定一个二叉树的根节点 root 和一个整数 targetSum 求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始也不需要在叶子节点结束但是路径方向必须是向下的只能从父节点到子节点。
示例 1 输入root [10,5,-3,3,2,null,11,3,-2,null,1], targetSum 8
输出3
解释和等于 8 的路径有 3 条如图所示。示例 2
输入root [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum 22
输出3提示:
二叉树的节点个数的范围是 [0,1000]-109 Node.val 109 -1000 targetSum 1000 解答
源代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public int pathSum(TreeNode root, int targetSum) {MapLong, Integer preSum new HashMap();preSum.put(0L, 1);return dfs(root, preSum, targetSum, 0);}public int dfs(TreeNode root, MapLong, Integer preSum, int targetSum, long cur) {if (root null) {return 0;}// res表示以当前节点为根节点的二叉树的节点做路径末尾有多少符合要求的路径int res 0;cur root.val;res preSum.getOrDefault(cur - targetSum, 0);preSum.put(cur, preSum.getOrDefault(cur, 0) 1);res dfs(root.left, preSum, targetSum, cur);res dfs(root.right, preSum, targetSum, cur);preSum.put(cur, preSum.get(cur) - 1);return res;}
}
总结
计算前缀和二叉树中前缀和定义为当前节点一直到根节点的路径上所有节点之和那么两节点的前缀和相减得到的结果便是两节点之间的路径和。
按照这个思路我们对二叉树进行深度优先遍历在遍历过程中将节点的前缀和存储起来。对于当前节点的前缀和cur查询是否存在cur - targetSum前缀和。
