我要招人

去企业版

首页 > 试题广场 >

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

[编程题]二叉树中和为某一值的路径(一)

热度指数：165709 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。

1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点

2.叶子节点是指没有子节点的节点

3.路径只能从父节点到子节点，不能从子节点到父节点

4.总节点数目为n

例如：
给出如下的二叉树， $\ sum=22$ ，

返回true，因为存在一条路径 $5\to 4\to 11\to 2$ 的节点值之和为 22

数据范围：

1.树上的节点数满足 $0 \le n \le 10000$

2.每个节点的值都满足 $|val| \le 1000$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

进阶：空间复杂度 $O(树的高度)$ ，时间复杂度 $O(n)$

示例1

输入

{5,4,8,1,11,#,9,#,#,2,7},22

输出

true

示例2

输入

{1,2},0

输出

false

示例3

输入

{1,2},3

输出

true

示例4

输入

{},0

输出

false

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Maokt

发表于 2021-07-06 11:02:20

精华题解此题解法可借鉴：二叉树根节点到叶子节点和为指定值的路径 https://blog.nowcoder.net/n/3ca862f49e6c409cb111db77c12932e8 算法思想一：递归解题思路：采用递归遍历二叉树的路径节点，同时计算二叉树路径节点的数字之和，当到达叶展开全文

有名

发表于 2021-07-15 22:00:06

精华题解思路本题实质上是一道二叉树搜索的问题，通过遍历搜索二叉树，从而判断二叉树节点中是否存在节点和为指定值的路径。方法一：前序遍历这里采用的是前序遍历的递归实现方法，即：根节点-左儿子-右儿子。具体思路如下图所示：具体代码如下： import java.util.*; /* * pub 展开全文

牛客题解官

发表于 2022-04-22 11:56:16

精华题解题目的主要信息：给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径路径定义为从树的根节点开始往下一直到叶子节点所经过的节点路径只能从父节点到子节点，不能从子节点到父节点举一反三：学习完本题的思路你可以解决如下题目： BM28. 二叉树展开全文

漫漫云天自翱翔

发表于 2021-07-05 13:13:13

精华题解题解一：先序遍历解题思路： 1.对树进行先序遍历。使用ans路径和。 2.如果ans> sum 或者ans!=sum&&到达叶子节点,那么就回溯(剪枝) 3. 找到合法路径，返回true; 展开全文

江南好___

发表于 2021-07-14 20:21:02

精华题解描述题目描述给定一个二叉树和一个值sum ，判断是否有从根节点到叶子节点的节点值之和等于sum的路径，示例输入：{1,2},0 返回值：false知识点：二叉树难度：⭐⭐ 题解解题思路二叉树的问题往往都能通过遍历和递归解决，只是递归相对遍历不好理解，但一旦掌握递归的诀窍，能节省很多行代展开全文

牛一霸

发表于 2021-07-05 00:10:37

精华题解题目：二叉树中是否存在节点和为指定值的路径描述：给定一个二叉树和一个值 sum，判断是否有从根节点到叶子节点的节点值之和等于 sum的路径，例如：给出如下的二叉树， sum=22，返回true，因为存在一条路径5→4→11→2的节点值之和为22 展开全文

如也201810022128875

发表于 2021-07-09 16:18:55

精华题解 NC9 二叉树中是否存在节点和为指定值的路径题目描述给定一个二叉树和一个值 sum，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径，方法一：暴力递归解题思路因为题目中所说的路径是从根节点到叶子节点所有节点走完，而二叉树里可以用前序遍历、中序遍历、后序遍历从根节点往下一条一条展开全文

数据结构和算法

发表于 2021-08-03 14:35:32

递归求解这题让判断从根节点到叶子节点的所有路径中，有没有和等于sum的，如果看过之前讲的《442，剑指 Offer-回溯算法解二叉树中和为某一值的路径》，再来看这一题就觉得这题有点简单了。第442题要求的是把所有的和等于sum的路径都打印出来，而这题只要判断有一个路径的和等于sum即可。我们可展开全文

学编程的蒟蒻

发表于 2022-02-25 21:47:43

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @ 展开全文

华科不平凡

发表于 2020-08-21 17:50:29

先序遍历，套模版就是了。 class Solution { public: /** * * @param root TreeNode类 * @param sum int整型 * @return bool布尔型 */ bool hasP 展开全文

passway

发表于 2022-01-07 20:53:59

# def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # 展开全文

牛客123100277号

发表于 2022-02-05 20:19:59

/** * struct TreeNode { * int val; * struct TreeNode *left; * & 展开全文

designeer

发表于 2021-11-06 11:32:35

思路本题实质上是一道二叉树搜索的问题，通过遍历搜索二叉树，从而判断二叉树节点中是否存在节点和为指定值的路径。方法一：前序遍历这里采用的是前序遍历的递归实现方法，即：根节点-左儿子-右儿子。具体思路如下图所示：展开全文

WANGwww

发表于 2022-02-22 14:30:31

解题思路临界条件：叶子节点（左右子树为空）满足条件：路径之和为sum 解题步骤左右子树同时递归查找，找到一个满足条件，即为找到，故左右子树的递归查找用“或”连接递归查找时，抛去根节点的值，左右子树继续向下查找当叶子节点且节点值等于sum找到注意临界条件注意审题，二叉树中的值展开全文

总之就是非常可爱

发表于 2022-02-22 14:44:20

//本题用深度优先遍历的方法比较简单 //每次到叶子节点时比较一下是否等于sum /** * struct TreeNode { * int val; * struct T 展开全文

小洋芋热爱NLP

发表于 2020-12-02 19:07:59

- 题目描述： - 题目链接： https://www.nowcoder.com/practice/508378c0823c423baa723ce448cbfd0c?tpId=188&&tqId=36560&rp=1&ru=/ta/job-code-high-wee 展开全文

牛客628476375号

发表于 2021-12-27 04:52:02

解题思路对于二叉树，任意给定节点到根节点之间的路径是唯一固定的。因此其对应的路径个vals的和也是唯一固定的。因此，可利用前序方式对二叉树进行遍历，途中将每个节点中的val值替换成其对应的路径各vals之和。遍历过程中，检查leaf节点的val是否等于sum。 #include <iostr 展开全文

问题信息

树 dfs

难度：

278条回答 866收藏 30332浏览

通过挑战的用户

查看代码

牛客30382...

2022-12-24 12:24:34
牛客74843...

2022-10-16 13:22:43
牛客57846...

2022-09-16 22:47:13
snailCl...

2022-09-16 20:51:09
牛客52528...

2022-09-16 20:42:25

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

输入

输出

输入

输出

输入

输出

输入

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题