给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。
1.该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点
2.总节点数目为n
3.保证最后返回的路径个数在整形范围内(即路径个数小于231-1)
数据范围:
假如二叉树root为{1,2,3,4,5,4,3,#,#,-1}，sum=6，那么总共如下所示，有3条路径符合要求
[编程题]二叉树中和为某一值的路径(三)
class Solution {
public:
int FindPath(TreeNode* root, int sum) {
if(!root) return 0;
return count(root,sum)+FindPath(root->left,sum)+FindPath(root->right,sum);
}
int count(TreeNode* root,int sum){
if(!root) return 0;
if(sum==root->val)
return 1+count(root->left,sum-root->val)+count(root->right,sum-root->val);
return count(root->left,sum-root->val)+count(root->right,sum-root->val);
}
};
发表于 2022-01-21 20:33:41
回复(0)
class Solution:
def __init__(self):
self.mp = {}
def dfs(self, root, sum, lsum):
if not root:
return 0
res = 0
tmp = root.val + lsum
if self.mp.__contains__(tmp - sum):
res += self.mp[tmp - sum]
if tmp in self.mp:
self.mp[tmp] += 1
else:
self.mp[tmp] = 1
res += self.dfs(root.left, sum, tmp)
res += self.dfs(root.right, sum, tmp)
self.mp[tmp] -= 1
return res
def FindPath(self , root: TreeNode, sum: int) -> int:
# write code here
self.mp[0] = 1
return self.dfs(root, sum, 0)
python实现的一次dfs+哈希表 时间复杂度o(n) 空间复杂度o(n)
发表于 2022-04-22 22:02:11
回复(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)
class Solution: # 以root为起始节点可得到的路径数 def getCount(self, root, count, sum): if not root: return # 这里必须先减去root的值，否则只有一个节点时会出问题 if sum - root.val == 0: count[0] += 1 self.getCount(root.left, count, sum - root.val) self.getCount(root.right, count, sum - root.val) def FindPath(self, root: TreeNode, sum: int) -> int: if not root: return 0 count = [0] self.getCount(root, count, sum) res = count[0] + self.FindPath(root.left, sum) + self.FindPath(root.right, sum) return res
发表于 2021-11-22 14:51:46
回复(0)
class Solution {
public:
int ans=0;
void find(TreeNode*root,int sum)
{
if(!root)return ;
if(sum-root->val==0)ans++;
find(root->left,sum-root->val);
find(root->right,sum-root->val);
}
int FindPath(TreeNode* root, int sum) {
// write code here
if(!root)return ans;
find(root,sum);
FindPath(root->left,sum);
FindPath(root->right,sum);
return ans;
}
};
发表于 2022-01-03 12:20:08
回复(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)
怎么没有一个人觉得题目的示例有问题？这个题的示例绝对有问题 我用笔做的跟题目给的不一样
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
vector<int>preorder_l;
vector<vector<int>>res;
void dfs(TreeNode *T){
if(!T) return;
preorder_l.push_back(T->val);
dfs(T->left);
dfs(T->right);
if(!T->left&&!T->right){
res.push_back(preorder_l);
}
preorder_l.pop_back();
}
int FindPath(TreeNode* root, int sum) {
dfs(root);
int count=0;
for(int i=0;i<res.size();i++){
for(int j=0;j<res[i].size();j++){
int sum_1=0;
for(int k=j;k<res[i].size();k++){
sum_1+=res[i][k];
if(sum_1==sum){
count++;
}
}
}
}
return count;
}
};
发表于 2022-06-09 16:08:36
回复(1)
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param sum int整型
* @return int整型
*/
int FindPath(TreeNode* root, int sum) {
// 时间复杂度O(N^2)，空间复杂度O(N)
if (root == nullptr) return 0;
return FindPath(root->left, sum) + FindPath(root->right, sum) + dfs(root, sum);
}
int dfs(TreeNode *root, int cur) {
if (root == nullptr) return 0;
int res = root->val == cur ? 1 : 0;
return res + dfs(root->left, cur - root->val) + dfs(root->right, cur - root->val);
}
};
发表于 2022-11-19 00:24:44
回复(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)
感觉不是那么完美的解法
# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param root TreeNode类 # @param sum int整型 # @return int整型 # class Solution: def FindPath(self , root: TreeNode, sum: int) -> int: # write code here collection = [] self.traverse1(root, collection) res = 0 for i in collection: for j in i: if j == sum: res += 1 return res def traverse1(self, root, collection): if root is None: return tmp = [] self.traverse2(root, 0, tmp) collection.append(tmp) self.traverse1(root.left, collection) self.traverse1(root.right, collection) def traverse2(self, root, now_res, num_arr): if root is None: return num_arr.append(now_res + root.val) self.traverse2(root.left, now_res + root.val, num_arr) self.traverse2(root.right, now_res + root.val, num_arr)
编辑于 2024-04-23 21:53:15
回复(0)
感觉题意说的不够清楚，没有讲明从一个父节点只能向一个子节点出发，最开始我还误解为{1,2,2,3,3,3,3},8这个用例该输出2
发表于 2024-01-16 13:18:37
回复(0)
#include <functional>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param sum int整型
* @return int整型
*/
int res = 0;
int FindPath(TreeNode* root, int sum) {
if(!root) return 0;
function<void (TreeNode*,int )> dfs = [&](TreeNode* root,int sum){
if(!root) return ;
if(sum == root->val) res++;
dfs(root->left , sum - root->val);
dfs(root->right , sum - root->val);
};
dfs(root,sum);
FindPath(root->left, sum);
FindPath(root->right, sum);
return res;
}
};
发表于 2023-11-06 17:17:17
回复(0)
int res = 0;
void dfs(TreeNode* root, int sum){
if(root == nullptr) return;
if(root->val == sum) res++;
dfs(root->left, sum - root->val);
dfs(root->right, sum - root->val);
}
int FindPath(TreeNode* root, int sum) {
// write code here
if(root == nullptr) return res;
dfs(root, sum);
FindPath(root->left, sum);
FindPath(root->right, sum);
return res;
}
发表于 2023-10-07 20:45:05
回复(0)
用HashMap存每个节点的路径，然后倒叙求和
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 int FindPath (TreeNode root, int sum) {
// write code here
int numberOfPath = 0;
if (root == null) {
return numberOfPath;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
HashMap<TreeNode, ArrayList<Integer>> pathMap =
new HashMap<TreeNode, ArrayList<Integer>>();
queue.offer(root);
pathMap.put(root, new ArrayList<Integer>());
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
ArrayList<Integer> path = new ArrayList<Integer>(pathMap.get(node));
path.add(node.val);
if (node.left != null) {
// System.out.println(node.val + ".left = " + node.left.val);
queue.offer(node.left);
pathMap.put(node.left, path);
}
if (node.right != null) {
// System.out.println(node.val + ".right = " + node.right.val);
queue.offer(node.right);
pathMap.put(node.right, path);
}
int sumOfPath = 0;
for (int j = path.size() - 1; j >= 0; j--) {
sumOfPath += path.get(j);
if (sumOfPath == sum) {
numberOfPath++;
}
}
}
}
return numberOfPath;
}
}
发表于 2023-10-02 17:01:49
回复(0)
该题是NC9 二叉树中和为某一值的路径(一)的延伸，这里可以在主函数里遍历树中每个结点，然后调用NC9题的解决方法即可。值得注意的是，因为不能找到一条路径就返回，因此把计数变量count做成类变量。
代码实现：
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param sum int整型
* @return int整型
*/
int count = 0;
public int FindPath (TreeNode root, int sum) {
// write code here
if(root==null){
return count;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()){
while(cur != null){
dfs(cur, sum);
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
cur = cur.right;
}
return count;
}
private void dfs(TreeNode root, int sum){
if(root == null){
return;
}
if(root.val == sum){
count++;
}
dfs(root.left, sum - root.val);
dfs(root.right, sum - root.val);
}
}
发表于 2023-09-27 16:16:26
回复(0)
#初见改了超久，本质是两重循环遍历，让每个节点都作为一次sum的第一个节点开始计算它的子树路径 class Solution: def FindPath(self , root: TreeNode, sum: int) -> int: # write code here if(root == None): return 0 count = 0 check = [] def bianli(root,sum): #前序遍历 递归版本 让每个root都作为第一个节点 nonlocal count #非局部变量，也即全局变量 if(root == None): return 0 sum = sum - root.val if(sum == 0): count += 1 #没有叶子节点限制也就是说sum==0也不能停，还要看后面的情况 bianli(root.left,sum) bianli(root.right,sum) sum = sum + root.val while(root != None&nbs***bsp;len(check)!=0): #前序遍历，非递归版本 if(root != None): bianli(root,sum) check.append(root) root = root.left else: root = check.pop() root = root.right return count
发表于 2023-09-23 16:16:42
回复(0)
# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param root TreeNode类 # @param sum int整型 # @return int整型 # class Solution: def FindPath(self, root: TreeNode, sum: int) -> int: # write code here if not root: return 0 # 每一个结点统计开始时，初始化累加器 self.count = 0 return self.dfs(root, sum) + \ self.FindPath(root.left, sum) + \ self.FindPath(root.right, sum) # 对结点进行深度遍历，遍历过程中遇到和为sum的路径，累加器count加1 count = 0 def dfs(self, root, sum): if not root: return 0 if sum == root.val: self.count += 1 self.dfs(root.left, sum - root.val) self.dfs(root.right, sum - root.val) # 返回累加器的值 return self.count
发表于 2023-07-05 11:25:59
回复(0)
class Solution:
def __init__(self) -> None:
self.res = 0
def FindPath(self , root: TreeNode, sum: int) -> int:
# write code here
if not root:
return 0
self.get_path(root,sum)
self.FindPath(root.left,sum)
self.FindPath(root.right,sum)
return self.res
def get_path(self, root, sum):
if not root:
return
if sum - root.val ==0:
self.res +=1
self.get_path(root.left,sum-root.val)
self.get_path(root.right,sum-root.val)
发表于 2023-04-06 21:46:57
回复(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号
