本文共 3615 字,大约阅读时间需要 12 分钟。
难度中等41
给定一棵二叉树,其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法,打印节点数值总和等于某个给定值的所有路径的数量。注意,路径不一定非得从二叉树的根节点或叶节点开始或结束,但是其方向必须向下(只能从父节点指向子节点方向)。
示例:
给定如下二叉树,以及目标和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
思路1:暴力dfs。
对于每个节点:
如果root==null 返回0
如果sum-root.val==0:那么返回 1+dfs(root.left,sum-root.val)+dfs(root.right,sum-root.val) //防止出现一条路径 1 2 -1 1 这种 和为3 但是要记两条
如果不满足上述条件,直接返回dfs(root.left,sum-root.val)+dfs(root.right,sum-root.val)
最后遍历每一个节点。
思路2:
这道题用到了一个概念,叫前缀和。就是到达当前元素的路径上,之前所有元素的和。
前缀和怎么应用呢?
如果两个数的前缀总和是相同的,那么这些节点之间的元素总和为零。进一步扩展相同的想法,如果前缀总和currSum,在节点A和节点B处相差target,则位于节点A和节点B之间的元素之和是target。
因为本题中的路径是一棵树,从根往任一节点的路径上(不走回头路),有且仅有一条路径,因为不存在环。(如果存在环,前缀和就不能用了,需要改造算法)
抵达当前节点(即B节点)后,将前缀和累加,然后查找在前缀和上,有没有前缀和currSum-target的节点(即A节点),存在即表示从A到B有一条路径之和满足条件的情况。结果加上满足前缀和currSum-target的节点的数量。然后递归进入左右子树。
左右子树遍历完成之后,回到当前层,需要把当前节点添加的前缀和去除。避免回溯之后影响上一层。因为思想是前缀和,不属于前缀的,我们就要去掉它。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public int Sum=0; public int dfs(TreeNode root,int sum) { if(root==null) return 0; if(sum-root.val==0) return 1+dfs(root.left,sum-root.val)+dfs(root.right,sum-root.val);//对于 1 -2 1 -1 if sum=-1 这条支路要记两根 //if(sum-root.val<0)//可能会出现负值 //return 0; return dfs(root.left,sum-root.val)+dfs(root.right,sum-root.val); } public int pathSum(TreeNode root, int sum) { if(root==null) return 0; return dfs(root,sum)+pathSum(root.left,sum)+pathSum(root.right,sum); }}
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public int pathSum(TreeNode root, int sum) { // key是前缀和, value是大小为key的前缀和出现的次数 MapprefixSumCount = new HashMap<>(); // 前缀和为0的一条路径 prefixSumCount.put(0, 1); // 前缀和的递归回溯思路 return recursionPathSum(root, prefixSumCount, sum, 0); } /** * 前缀和的递归回溯思路 * 从当前节点反推到根节点(反推比较好理解,正向其实也只有一条),有且仅有一条路径,因为这是一棵树 * 如果此前有和为currSum-target,而当前的和又为currSum,两者的差就肯定为target了 * 所以前缀和对于当前路径来说是唯一的,当前记录的前缀和,在回溯结束,回到本层时去除,保证其不影响其他分支的结果 * @param node 树节点 * @param prefixSumCount 前缀和Map * @param target 目标值 * @param currSum 当前路径和 * @return 满足题意的解 */ private int recursionPathSum(TreeNode node, Map prefixSumCount, int target, int currSum) { // 1.递归终止条件 if (node == null) { return 0; } // 2.本层要做的事情 int res = 0; // 当前路径上的和 currSum += node.val; //---核心代码 // 看看root到当前节点这条路上是否存在节点前缀和加target为currSum的路径 // 当前节点->root节点反推,有且仅有一条路径,如果此前有和为currSum-target,而当前的和又为currSum,两者的差就肯定为target了 // currSum-target相当于找路径的起点,起点的sum+target=currSum,当前点到起点的距离就是target res += prefixSumCount.getOrDefault(currSum - target, 0); // 更新路径上当前节点前缀和的个数 prefixSumCount.put(currSum, prefixSumCount.getOrDefault(currSum, 0) + 1); //---核心代码 // 3.进入下一层 res += recursionPathSum(node.left, prefixSumCount, target, currSum); res += recursionPathSum(node.right, prefixSumCount, target, currSum); // 4.回到本层,恢复状态,去除当前节点的前缀和数量 prefixSumCount.put(currSum, prefixSumCount.get(currSum) - 1); return res; }}
每天刷一道题,真的是快乐源泉了,可是快要考试了,还有好多事要忙,真想做个没感情的刷题机器。。。