首页 > 试题广场 >

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

[编程题]二叉树中和为某一值的路径(一)
  • 热度指数：169962 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2.叶子节点是指没有子节点的节点
3.路径只能从父节点到子节点，不能从子节点到父节点
4.总节点数目为n

例如：
给出如下的二叉树，，

返回true，因为存在一条路径 的节点值之和为 22

数据范围：
1.树上的节点数满足
2.每 个节点的值都满足
要求：空间复杂度 ，时间复杂度
进阶：空间复杂度 ，时间复杂度
示例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，点此查看相关信息
算法知识视频讲解
查看答案及解析
添加回答
C
陈让然头像 陈让然
感觉二叉树很多问题都可以用递归解决，用遍历太复杂了
该题中，sum=每层经过结点值的和（直到遇见叶子结点） 
bool hasPathSum(struct TreeNode* root, int sum ) 
{
    // write code here
    //数不存在
    if(!root)
    {
        return false;
    }
    //发现叶子结点，且路径符合
    if(!root->left&&!root->right&&!(sum-root->val))
    {
        return true;
    }
    //若存在左/右结点，每次向下一个结点延伸，要减去当前结点值
    return hasPathSum(root->left,sum-root->val)||hasPathSum(root->right, sum-root->val);
}

发表于 2023-11-15 20:18:01 回复(0)
C
芸某头像 芸某
注意是到叶子节点而不是存在路径。。
递归 
bool hasPathSum(struct TreeNode* root, int sum ) {
    if(root==NULL){
        return false;
    }
    if(root->left == NULL&&root->right==NULL&&sum - root->val==0){
        return true;
    }
    if(hasPathSum(root->left,sum - root->val)){
        return true;
    }
    if(hasPathSum(root->right,sum - root->val)){
        return true;
    }
    return false;
}



发表于 2023-09-21 20:30:01 回复(0)
C
小熊猫的黑眼圈头像 小熊猫的黑眼圈
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @param sum int整型
 * @return bool布尔型
 */
bool hasPathSum(struct TreeNode* root, int sum )
{
    // write code here
    if(!root)
    {
        return false;
    }
    static int pathsum;
    bool left;
    pathsum=pathsum+root->val;
    int tempsum=pathsum;
    left=hasPathSum(root->left,sum);
    if(left)
    {
        return true;
    }
    if(root->right)
    {
        pathsum=tempsum;
        hasPathSum(root->right,sum);
    }
    if(sum==pathsum)
    {
        return true;
    }
    return false;
}
发表于 2023-07-08 10:22:42 回复(0)
C
碧秋头像 碧秋
深度周游中的先序遍历 
bool calPathLen(TreeNode* root,int sum,int cur){
	if(root==NULL)//递归出口，表示走到底还没找到则false
		return false;
	cur+=root->val;
	if(cur==sum && root->left==NULL && root->right==NULL)//等于指定的sum，并且是计算到叶结点
		return true;
	return calPathLen(root->left,sum,cur)||calPathLen(root->right,sum,cur);
}

bool hasPathSum(struct TreeNode* root, int sum ) {
    return calPathLen(root,sum,0);
}


发表于 2023-03-10 14:24:22 回复(0)
C
JayneChou头像 JayneChou 
#include <stdbool.h>
bool hasPathSum(struct TreeNode* root, int sum ) {
    if(root){
        //找到符合条件的路径
        if(root->val == sum && !root->left && !root->right){
            return true;
        } else {
            //如果还没到目标路径的话
            return hasPathSum(root->left, sum - root->val) || 
                hasPathSum(root->right, sum - root->val);
        }
    } else {
        //如果是目标路径就不会进入这里，肯定在这之前就返回true
        //所以如果某一路径递归到根结点为null那肯定不是目标路径
        return false;
    }
}

发表于 2023-02-26 22:50:31 回复(0)
C
牛客82035003号头像 牛客82035003号
使用bool前要加上头文件<stdbool.h>，否则不能识别bool. 
#include <stdbool.h>
bool  hasPathSum(struct TreeNode* root, int sum ) {
    if(root == NULL)
        return false;
    sum = sum - root->val;
    if(sum == 0 && root->left == NULL && root->right == NULL)
        return true;
    return hasPathSum(root->left, sum) || hasPathSum(root->right, sum);
    
}


发表于 2022-02-17 12:10:40 回复(0)
C
小小鼠人可笑可笑头像 小小鼠人可笑可笑 
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @param sum int整型 
 * @return bool布尔型
 */
#include<stdbool.h>
bool hasPathSum(struct TreeNode* root, int sum ) {
    if(root==NULL) return false;
    else if(sum==root->val&&root->left==NULL&&root->right==NULL) return true;
    else return(hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val) );
}

发表于 2022-01-30 13:43:43 回复(0)
提交观点

问题信息

树 dfs
难度：
7条回答 30814浏览

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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