力扣112路径总和

简介: 力扣112路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。

叶子节点 是指没有子节点的节点。

示例 1:


输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22

输出:true

解释:等于目标和的根节点到叶节点路径如上图所示。

示例 2:


输入:root = [1,2,3], targetSum = 5

输出:false

解释:树中存在两条根节点到叶子节点的路径:

(1 --> 2): 和为 3

(1 --> 3): 和为 4

不存在 sum = 5 的根节点到叶子节点的路径。

示例 3:


输入:root = [], targetSum = 0

输出:false

解释:由于树是空的,所以不存在根节点到叶子节点的路径。


提示:


树中节点的数目在范围 [0, 5000] 内

-1000 <= Node.val <= 1000

-1000 <= targetSum <= 1000


来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/path-sum

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

//第一种方法是将路径值之和相加再比较
class Solution {
public: 
    bool aa = false;
    void sumcount(TreeNode*root,vector<int>& ve,int targetSum)
    {
        if(aa==true)return;
        if(root==nullptr)return;
        ve.push_back(root->val);
        if(root->left==nullptr&&root->right==nullptr)
        {
            int size = ve.size();
            int sum= 0;
            for(int i=0;i<size;i++)
            {
                sum+=ve[i];
            }
            if(sum==targetSum)aa=true;
        }
        if(root->left&&aa==false)
        {
            sumcount(root->left,ve,targetSum);
            ve.pop_back();
        }
        if(root->right&&aa==false)
        {
            sumcount(root->right,ve,targetSum);
            ve.pop_back();
        }
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root==nullptr)return false;
        vector<int>ve;
        sumcount(root,ve,targetSum);
        return aa;
    }
};
//第二种是直接递归的时候就将当前节点的值减掉
class solution {
private:
    bool traversal(treenode* cur, int count) {
        if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点,并且计数为0
        if (!cur->left && !cur->right) return false; // 遇到叶子节点直接返回
        if (cur->left) { // 左
            count -= cur->left->val; // 递归,处理节点;
            if (traversal(cur->left, count)) return true;
            count += cur->left->val; // 回溯,撤销处理结果
        }
        if (cur->right) { // 右
            count -= cur->right->val; // 递归,处理节点;
            if (traversal(cur->right, count)) return true;
            count += cur->right->val; // 回溯,撤销处理结果
        }
        return false;
    }
public:
    bool haspathsum(treenode* root, int sum) {
        if (root == null) return false;
        return traversal(root, sum - root->val);
    }
};
目录
相关文章
|
11月前
【LeetCode 35】112.路径总和
【LeetCode 35】112.路径总和
92 0
|
算法 Unix 测试技术
力扣经典150题第五十二题:简化路径
力扣经典150题第五十二题:简化路径
128 0
|
4月前
|
Go 开发者 索引
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣33 / 81/ 153/154)(Go语言版)
本文深入探讨了LeetCode中四道关于「搜索旋转排序数组」的经典题目,涵盖了无重复和有重复元素的情况。通过二分查找的变形应用,文章详细解析了每道题的解题思路和Go语言实现代码。关键点包括判断有序区间、处理重复元素以及如何缩小搜索范围。文章还总结了各题的异同,并推荐了类似题目,帮助读者全面掌握二分查找在旋转数组中的应用。无论是初学者还是有经验的开发者,都能从中获得实用的解题技巧和代码实现方法。
254 14
|
5月前
|
Go
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣437 / 236 )(Go语言版)
本文深入探讨二叉树中路径与祖先问题,涵盖两道经典题目:LeetCode 437(路径总和 III)和236(最近公共祖先)。对于路径总和 III,文章分析了双递归暴力解法与前缀和优化方法,后者通过哈希表记录路径和,将时间复杂度从O(n²)降至O(n)。在最近公共祖先问题中,采用后序遍历递归查找,利用“自底向上”的思路确定最近公共祖先节点。文中详细解析代码实现与核心要点,帮助读者掌握深度追踪技巧,理解树结构中路径与节点关系的本质。这类问题在面试中高频出现,掌握其解法意义重大。
118 4
|
5月前
|
算法 Go
【LeetCode 热题100】深入理解二叉树结构变化与路径特性(力扣104 / 226 / 114 / 543)(Go语言版)
本博客深入探讨二叉树的深度计算、结构变换与路径分析,涵盖四道经典题目:104(最大深度)、226(翻转二叉树)、114(展开为链表)和543(二叉树直径)。通过递归与遍历策略(前序、后序等),解析每题的核心思路与实现方法。结合代码示例(Go语言),帮助读者掌握二叉树相关算法的精髓。下一讲将聚焦二叉树构造问题,欢迎持续关注!
135 10
|
11月前
【LeetCode 36】113.路径总和II
【LeetCode 36】113.路径总和II
87 0
|
机器人 Python
【Leetcode刷题Python】62. 不同路径
LeetCode 62题 "不同路径" 的Python解决方案,使用动态规划算法计算机器人从网格左上角到右下角的所有可能路径数量。
199 0
|
存储 SQL 算法
LeetCode题目113:多种算法实现 路径总和ll
LeetCode题目113:多种算法实现 路径总和ll
|
Python
【Leetcode刷题Python】113. 路径总和 II
LeetCode上113号问题"路径总和 II"的Python实现,通过深度优先搜索来找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
95 3
【Leetcode刷题Python】113. 路径总和 II
|
存储 Python
【Leetcode刷题Python】64. 最小路径和
一种使用动态规划解决LeetCode上64题“最小路径和”的Python实现方法,通过维护一个一维数组来计算从网格左上角到右下角的最小路径总和。
78 1
【Leetcode刷题Python】64. 最小路径和