首页 > 试题广场 >

二叉树中和为某一值的路径(三)

[编程题]二叉树中和为某一值的路径(三)
  • 热度指数：27723 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。
1.该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点
2.总节点数目为n
3.保证最后返回的路径个数在整形范围内(即路径个数小于231-1)

数据范围:



假如二叉树root为{1,2,3,4,5,4,3,#,#,-1}，sum=6，那么总共如下所示，有3条路径符合要求

示例1

输入

{1,2,3,4,5,4,3,#,#,-1},6

输出

3

说明

如图所示，有3条路径符合
示例2

输入

{0,1},1

输出

2
示例3

输入

{1,#,2,#,3},3

输出

2

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2022-04-25 18:31:13
精华题解 题目的主要信息： 给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点，如下图所示： 举一反三： 学习完本题的思路你可以解决如下题目： JZ82. 二叉树中和为某一值的路 展开全文
去ta的博客 赞 (13) 回复(1) 收起
头像 摸鱼学大师
发表于 2021-12-04 14:24:31
题目的主要信息： 给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点，如下图所示： 方法一：两次dfs 具体做法： 可以使用两次dfs解决，第一次dfs遍历二叉树每个结 展开全文
去ta的博客 赞 (23) 回复(3) 收起
头像 代码界的小白
发表于 2021-12-17 10:27:32
题目主要信息 给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点，如下图所示： 方法一：两次dfs过程 具体方法 可以使用两次dfs解决，第一次dfs遍历二叉树每个结点 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 蓉城小晋
发表于 2021-11-25 12:51:59
```/* * function TreeNode(x) { * this.val = x; * this.left = null; * this.right = null; * } */ /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 牛客433600638号
发表于 2021-11-10 17:19:25
public class Solution { public int FindPath (TreeNode root, int sum) { if(root == null) return 0; return helper(root, sum) + 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 godhands
发表于 2022-03-09 07:51:04
描述 题目描述 首先是给定了我们的一颗树, 我们要判断有多少条的路径可以满足我们路径的总和的值等于我们的sumsumsum, 然后我们根节点可以是任意的, 然后我们必须是从父亲节点到孩子节点 题解 解法一: 每一次都作为根节点 实现思路 我们穷举的所有的节点, 然后以每一个节点检测向下延申的路径有多 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 雾里看花花里看雾
发表于 2023-04-13 22:39:05
二叉树中和为某一值的路径(三)：最直观的想法是，首先编写一个以某一节点为路径起始节点的求给定值的函数，其相对于(一)的区别是终止条件部分不要求必须是叶子节点且对应的执行操作是将满足要求的路径数量加一，而且这个终止部分不能直接返回，因为其路径中可能存在负值，从而出现正负抵消的情况。然后由于起始节点不一 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛枕忆
发表于 2021-12-10 17:30:48
class Solution { int dfs(TreeNode *proot,int sum){//函数功能是找出树中带根结点且和为sum的路径，为了保证路径的连通性 if(!proot)return 0; if(proot->val==sum)re 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 呆喵挠琴
发表于 2021-12-18 17:53:27
题目的主要信息： 给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点 方法一： 采用递归。FindPath中用bfs计算以当前结点作为起点满足条件的路径个数，然后递归计 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 designeer
发表于 2021-11-07 16:30:25
import sys   sys.setrecursionlimit(100000) class Solution:     def __init__(self):    &nbs 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 dijkstra_
发表于 2021-11-26 11:25:24
class Solution { public: int recur(TreeNode* root, int sum, bool isHaveRoot) { if(root == NULL) return 0; int count = 0; 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

树
上传者：牛客301499号
难度：
53条回答 1962浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号