陕西省住房和城乡建设部网站,html5餐饮美食订餐微官网wap手机网站模板整站下载,做徽章的企业网站,做一个跨境电商网站给定一棵二叉树#xff0c;其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法#xff0c;打印节点数值总和等于某个给定值的所有路径的数量。注意#xff0c;路径不一定非得从二叉树的根节点或叶节点开始或结束#xff0c;但是其方向必须向下(只能从父节点指向子…给定一棵二叉树其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法打印节点数值总和等于某个给定值的所有路径的数量。注意路径不一定非得从二叉树的根节点或叶节点开始或结束但是其方向必须向下(只能从父节点指向子节点方向)。示例:
给定如下二叉树以及目标和 sum 225/ \4 8/ / \11 13 4/ \ / \7 2 5 1
返回:3
解释和为 22 的路径有[5,4,11,2], [5,8,4,5], [4,11,7]
代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {int tar, cnt 0;public int pathSum(TreeNode root, int sum) {tar sum;Sum(root, 0, new LinkedList());return cnt;}public void Sum(TreeNode root, int sum, LinkedListInteger res) {//dfsif (root null) return;res.add(root.val);cnt um(res);Sum(root.left, sum root.val, res);Sum(root.right, sum root.val, res);res.removeLast();}public int um(LinkedListInteger res) {//找当前数组符合的连续子数组int temp 0, r 0;for (int i res.size() - 1; i 0; i--) {r res.get(i);if (r tar) temp;}return temp;}
}递归前缀和回溯代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {int tar;public int pathSum(TreeNode root, int sum) {tar sum;HashMapInteger,Integer mapnew HashMap();map.put(0,1);//节点本身也算路径return helper(root, 0,map);}public int helper(TreeNode root, int sum, HashMapInteger,Integer map) {if (root null) return 0;int cnt0;int ressumroot.val;cnt map.getOrDefault(res-tar,0);//符合的前缀和出现的次数就是路径的数量map.put(res,map.getOrDefault(res,0)1);if(root.left!null) cnthelper(root.left, res, map);if(root.right!null) cnthelper(root.right, res, map);map.put(res,map.get(res)-1);//回溯return cnt;}
}
