leetcode 112 路径总和

简介: leetcode 112 路径总和

路径总和


fe50fdfac02549088fbc41dc51203a40.png

递归法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool result = false;
    void getsum(TreeNode* cur, int targetSum , int sum)
    {
        if(cur==nullptr)return;
        sum += cur->val;
        //找到叶子节点的和与目标相符
        if(cur->left==nullptr && cur->right==nullptr &&sum == targetSum) result = true;
        getsum(cur->left,  targetSum ,  sum);
        getsum(cur->right,  targetSum ,  sum);
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root==nullptr) return false;
        getsum(root , targetSum , 0);
        return result;
    }
};


二刷

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool result = false;
    void back_trak(TreeNode* cur , int targetSum  , int sum)
    {
        if(cur == nullptr || result == true) return;
        if((sum + cur->val) == targetSum && cur->left==nullptr && cur->right==nullptr ) result = true;
        back_trak(cur->left,targetSum , sum + cur->val );
        back_trak(cur->right,targetSum , sum + cur->val );
        return;
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == nullptr ) return false;
        back_trak(root , targetSum , 0);
        return result;
    }
};
相关文章
|
3月前
【LeetCode 35】112.路径总和
【LeetCode 35】112.路径总和
35 0
|
6月前
|
算法 Unix 测试技术
力扣经典150题第五十二题:简化路径
力扣经典150题第五十二题:简化路径
54 0
|
3月前
【LeetCode 36】113.路径总和II
【LeetCode 36】113.路径总和II
36 0
|
5月前
|
机器人 Python
【Leetcode刷题Python】62. 不同路径
LeetCode 62题 "不同路径" 的Python解决方案,使用动态规划算法计算机器人从网格左上角到右下角的所有可能路径数量。
80 0
|
7月前
|
存储 SQL 算法
LeetCode题目113:多种算法实现 路径总和ll
LeetCode题目113:多种算法实现 路径总和ll
|
3月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
31 0
|
5月前
|
Python
【Leetcode刷题Python】113. 路径总和 II
LeetCode上113号问题"路径总和 II"的Python实现,通过深度优先搜索来找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
46 3
【Leetcode刷题Python】113. 路径总和 II
|
5月前
|
存储 Python
【Leetcode刷题Python】64. 最小路径和
一种使用动态规划解决LeetCode上64题“最小路径和”的Python实现方法,通过维护一个一维数组来计算从网格左上角到右下角的最小路径总和。
36 1
【Leetcode刷题Python】64. 最小路径和
|
5月前
|
存储 算法 Linux
LeetCode第71题简化路径
文章讲述了LeetCode第71题"简化路径"的解题方法,利用栈的数据结构特性来处理路径中的"."和"..",实现路径的简化。
LeetCode第71题简化路径
|
5月前
|
算法
LeetCode第64题最小路径和
LeetCode第64题"最小路径和"的解题方法,运用动态规划思想,通过构建一个dp数组来记录到达每个点的最小路径和,从而高效求解。
LeetCode第64题最小路径和