给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。
1.该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点
2.总节点数目为n
3.保证最后返回的路径个数在整形范围内(即路径个数小于231-1)
数据范围:
假如二叉树root为{1,2,3,4,5,4,3,#,#,-1}，sum=6，那么总共如下所示，有3条路径符合要求
[编程题]二叉树中和为某一值的路径(三)
解题思路: 题目中说的意思是任意路径的和为 sum 即可, 限制条件是只能从父节点到子节点, 因此所有的节点都可以当做是一个起始点, 那么就得遍历所有的节点, 这时候我们可以使用层序遍历, 遍历到某个节点的时候, 对这个节点进行 路径的遍历(dfs).
总结:
- 先进行层序遍历, 目的是能够遍历到所有的节点, 并且所有的节点都可以当做是一个起始点;
- 层序遍历到某个节点, 则针对这个节点进行深度优先遍历, 得出路径.
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param sum int整型
* @return int整型
*/
int res = 0;
public void getPath(TreeNode cur, int sum) {
if (cur == null) {
return;
}
sum-=cur.val;
if (sum == 0) {
res++;
}
getPath(cur.left, sum);
getPath(cur.right, sum);
}
public int FindPath (TreeNode root, int sum) {
// write code here
if (root == null) {
return 0;
}
Queue<TreeNode> que = new ArrayDeque<>();
que.add(root);
while (!que.isEmpty()) {
int n = que.size();
for (int i = 0; i < n; i++) {
TreeNode cur = que.poll();
getPath(cur, sum);
if (cur.left != null) {
que.add(cur.left);
}
if (cur.right != null) {
que.add(cur.right);
}
}
}
return res;
}
}
发表于 2022-09-24 10:00:48
回复(0)
import java.util.*;
public class Solution {
int res = 0;
int target = 0;
public int FindPath (TreeNode root, int sum) {
target = sum;
if (root == null) return 0;
midOrder(root);
return res;
}
private void midOrder(TreeNode root) {
if (root != null) {
midOrder(root.left);
bfs(root, 0);
midOrder(root.right);
}
}
private void bfs(TreeNode root, int sum) {
if (root == null) return;
if (sum + root.val == target) {
res ++;
}
bfs(root.left, sum + root.val);
bfs(root.right, sum + root.val);
}
}
发表于 2022-09-14 11:23:10
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;l
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param sum int整型
* @return int整型
*/
//利用前缀和解决
public int FindPath (TreeNode root, int sum) {
if(root==null && sum!=0) return 0;
HashMap<Long,Integer> map=new HashMap<>();
map.put(0L,1); //给每个节点自己凑和的机会
int count=0;
count=digui(root,map,sum,0);
return count;
}
/**
cur 到目前位置,根节点到本节点时候的前缀和
*/
public int digui(TreeNode root,HashMap<Long,Integer> map,int sum,long cur){
if(root==null) return 0;
cur+=root.val;
int res=map.getOrDefault(cur-sum,0);
map.put(cur,map.getOrDefault(cur,0)+1);
res+=digui(root.left,map,sum,cur);
res+=digui(root.right,map,sum,cur);
map.put(cur,map.getOrDefault(cur,0)-1);
return res;
}
}
发表于 2022-08-15 09:01:46
回复(1)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param root TreeNode类
* @param sum int整型
* @return int整型
*/
int res = 0;
public int FindPath(TreeNode root, int sum) {
if (root == null) {
return res;
}
FindPath(root.left, sum);
show(root,0,sum);
FindPath(root.right, sum);
return res;
}
public void show(TreeNode node, int now ,int sum) {
now += node.val;
if (now == sum) {
res++;
}
if (node.left != null) {
show(node.left,now,sum);
}
if (node.right != null) {
show(node.right,now,sum);
}
}
}
发表于 2022-07-01 17:47:12
回复(0)
不需要从根节点开始，也不需要到叶子结点结束。
所以每个结点都可以作为根节点，然后进行dfs。所以有两个递归函数。
需要注意的是在dfs中，当sum减为0时不能返回和中断，因为后面还可能有元素满足条件。
所以只能使用res放在外面，当sum==0时res++。
public class Solution {
//当sum为0时不能返回，所以就只能声明在外面在递归里面+1
int res = 0;
public int FindPath (TreeNode root, int sum) {
if(root == null){
return 0;
}
dfs(root, sum);
FindPath(root.left, sum);
FindPath(root.right, sum);
return res;
}
public void dfs (TreeNode root, int sum) {
if(root == null){
return ;
}
sum -= root.val;
//当sum为0时不能返回，因为后面也可能会有符合条件的
if(sum == 0){
res++;
}
dfs(root.left, sum);
dfs(root.right, sum);
}
}
发表于 2022-03-24 15:32:58
回复(0)
java 前缀和 配合 dfs
public class Solution {
private int ans = 0;
private int preSum = 0;
HashMap<Integer, Integer> map;
public int FindPath (TreeNode root, int sum) {
// write code here
if (root == null) {
return 0;
}
map = new HashMap<>();
map.put(0, 1);
process(root, sum);
return ans;
}
public void process(TreeNode root, int sum) {
if (root == null) {
return;
}
preSum += root.val;
if (map.containsKey(preSum - sum)) {
ans += map.get(preSum - sum);
}
if (map.containsKey(preSum)) {
map.put(preSum, map.get(preSum) + 1);
}else {
map.put(preSum, 1);
}
process(root.left, sum);
process(root.right, sum);
map.put(preSum, map.get(preSum) - 1);
preSum -= root.val;
}
}
发表于 2022-03-09 21:30:06
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param sum int整型
* @return int整型
*/
private int pathNum = 0;
public int FindPath (TreeNode root, int sum) {
// write code here
if (root == null) return pathNum;
dfs(root, sum);
return pathNum;
}
public void pathFromOneNode (TreeNode root, int expectedNum) {
if (root == null) return;
if (root.val == expectedNum) pathNum++;
if (root.left != null) {
pathFromOneNode(root.left, expectedNum - root.val);
}
if (root.right != null) {
pathFromOneNode(root.right, expectedNum - root.val);
}
}
public void dfs(TreeNode root, int expectedNum){
pathFromOneNode(root, expectedNum);
if (root.left != null) dfs(root.left, expectedNum);
if (root.right != null) dfs(root.right, expectedNum);
}
}
发表于 2022-03-07 23:18:45
回复(0)
private int path;
public int FindPath (TreeNode root, int sum) {
if (root == null) {
return 0;
}
// write code here
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode t = stack.pop();
visit(t, sum);
if (t.right != null) {
stack.push(t.right);
}
if (t.left != null) {
stack.push(t.left);
}
}
return path;
}
private void visit(TreeNode root, int sum) {
if (root == null) {
return;
}
sum -= root.val;
if (sum == 0) {
path++;
}
visit(root.left, sum);
visit(root.right, sum);
}
发表于 2022-03-02 23:51:00
回复(0)
public class Solution {
public int FindPath (TreeNode root, int sum) {
// write code here
if(root == null) return 0;
int temp = Find(root.left,sum-root.val)+Find(root.right,sum-root.val)+FindPath(root.left,sum)+FindPath(root.right,sum);
if(sum == root.val) return temp + 1;
else return temp;
}
public int Find(TreeNode root, int sum){
if(root == null) return 0;
int temp = Find(root.left,sum-root.val) + Find(root.right,sum-root.val);
if(root.val == sum) return temp + 1;
else return temp;
}
}
public int FindPath (TreeNode root, int sum) {
// write code here
if(root == null) return 0;
int temp = Find(root.left,sum-root.val)+Find(root.right,sum-root.val)+FindPath(root.left,sum)+FindPath(root.right,sum);
if(sum == root.val) return temp + 1;
else return temp;
}
public int Find(TreeNode root, int sum){
if(root == null) return 0;
int temp = Find(root.left,sum-root.val) + Find(root.right,sum-root.val);
if(root.val == sum) return temp + 1;
else return temp;
}
}
发表于 2022-01-23 11:36:51
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param sum int整型
* @return int整型
*/
public static int res = 0;//统计路径个数
public int FindPath (TreeNode root, int sum) {
if(root == null){
return 0;
}
show(root,sum);
return res;
}
//遍历每个节点
public void show(TreeNode root, int sum){
if(root == null){
return;
}
func(root,0,sum);
if(root.left != null){
show(root.left,sum);
}
if(root.right != null){
show(root.right,sum);
}
}
//对传进来的节点为根，进行查找，找到满足条件的路径，并记录结果。
//当每条路走到叶子节点处，就返回
public void func(TreeNode root, int count,int sum){
count +=root.val;
if(sum == count){
res=res+1;
}
if(root.left != null ){
func(root.left,count,sum);
}
if(root.right != null ){
func(root.right,count,sum);
}
if(root.left == null && root.left == null){
return;
}
}
}
发表于 2021-12-09 14:27:32
回复(0)
public int FindPath (TreeNode root, int sum) {
// write code here
// FindPath 方法定义为从 root 节点开始，必须包括 root 节点，有多少路径的和为 sum
if (root == null) {
return 0;
}
dfs(root, sum, 0);
FindPath(root.left, sum);
FindPath(root.right, sum);
return ans;
}
private int ans;
public void dfs(TreeNode root, int sum, int target) {
if (root == null) {
return ;
}
target += root.val;
if (target == sum) {
ans ++;
}
dfs(root.left, sum, target);
dfs(root.right, sum, target);
target -= root.val;
}
发表于 2021-11-27 09:56:06
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param sum int整型
* @return int整型
*/
int num; //总数量
public int FindPath (TreeNode root, int sum) {
if (root==null) return num;
Deque<TreeNode> deque = new ArrayDeque<>();
deque.add(root);
while (!deque.isEmpty())
{
int size = deque.size();
for (int i = 0; i < size; ++i)
{
TreeNode pollNode = deque.poll();
toFindPath(pollNode,sum-pollNode.val);
if (pollNode.left!=null) deque.add(pollNode.left);
if (pollNode.right!=null) deque.add(pollNode.right);
}
}
return num;
}
private void toFindPath(TreeNode root, int target)
{
if (target==0)
{
++num;
}
if(root.left!=null) toFindPath(root.left,target-root.left.val);
if(root.right!=null) toFindPath(root.right,target-root.right.val);
}
}
发表于 2021-11-25 10:28:40
回复(0)
public class JZ84_FindPath {
int key = 0;
public int FindPath (TreeNode root, int sum) {
if (root == null) return key;
find(root,sum);
FindPath(root.left,sum);
FindPath(root.right,sum);
return key;
}
public void find(TreeNode root, int sum){
if (root == null) return;
sum -= root.val;
if (sum == 0) key++;
find(root.left,sum);
find(root.right,sum);
}
}
发表于 2021-11-04 21:10:14
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-09-16 11:26:59
-
2022-09-16 03:24:43
-
2022-09-15 23:29:11
-
2022-09-15 23:22:42
-
2022-09-15 22:53:44
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
