【LeetCode 35】112.路径总和

简介: 【LeetCode 35】112.路径总和

一、题意

二、思考过程

方法:递归+深度优先遍历 dfs

class Solution {
private:
    //1.
    bool traversal(TreeNode* cur, int count) {
        //2.
        if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点,并且计数为0,满足目标和
        if (!cur->left && !cur->right) return false; // 遇到叶子节点直接返回
        //3.
        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);
    }
};
ersal(root, sum - root->val);
    }
};


目录
相关文章
|
3月前
|
算法 Unix 测试技术
力扣经典150题第五十二题:简化路径
力扣经典150题第五十二题:简化路径
35 0
|
3天前
【LeetCode 36】113.路径总和II
【LeetCode 36】113.路径总和II
12 0
|
2月前
|
机器人 Python
【Leetcode刷题Python】62. 不同路径
LeetCode 62题 "不同路径" 的Python解决方案,使用动态规划算法计算机器人从网格左上角到右下角的所有可能路径数量。
59 0
|
4月前
|
存储 SQL 算法
LeetCode题目113:多种算法实现 路径总和ll
LeetCode题目113:多种算法实现 路径总和ll
|
3天前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
6 0
|
2月前
|
Python
【Leetcode刷题Python】113. 路径总和 II
LeetCode上113号问题"路径总和 II"的Python实现,通过深度优先搜索来找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
38 3
【Leetcode刷题Python】113. 路径总和 II
|
2月前
|
存储 Python
【Leetcode刷题Python】64. 最小路径和
一种使用动态规划解决LeetCode上64题“最小路径和”的Python实现方法,通过维护一个一维数组来计算从网格左上角到右下角的最小路径总和。
28 1
【Leetcode刷题Python】64. 最小路径和
|
2月前
|
存储 算法 Linux
LeetCode第71题简化路径
文章讲述了LeetCode第71题"简化路径"的解题方法,利用栈的数据结构特性来处理路径中的"."和"..",实现路径的简化。
LeetCode第71题简化路径
|
2月前
|
算法
LeetCode第64题最小路径和
LeetCode第64题"最小路径和"的解题方法,运用动态规划思想,通过构建一个dp数组来记录到达每个点的最小路径和,从而高效求解。
LeetCode第64题最小路径和
|
2月前
|
算法 JavaScript Python
【Leetcode刷题Python】79. 单词搜索和剑指 Offer 12. 矩阵中的路径
Leetcode第79题"单词搜索"的Python解决方案,使用回溯算法在给定的二维字符网格中搜索单词,判断单词是否存在于网格中。
28 4