[LeetCode] 112、路径总和
程序员文章站
2022-05-20 16:13:47
...
题目描述
给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
示例:
给定如下二叉树,以及目标和 sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
参考代码
常规题,很经典
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool hasPathSum(TreeNode* root, int target) {
hasPath = false;
int sum = 0;
hasPathSumRecursively(root, sum, target);
return hasPath;
}
void hasPathSumRecursively(TreeNode* root, int &sum, int target){
if(root == nullptr)
return;
sum += root->val;
if(root->left == nullptr && root->right == nullptr){
if(sum == target)
hasPath = true;
}
hasPathSumRecursively(root->left, sum, target);
hasPathSumRecursively(root->right, sum, target);
sum -= root->val;
}
private:
bool hasPath;
};
推荐阅读
-
【leetcode 简单】 第一百五十题 两个列表的最小索引总和
-
荐 LeetCode 120. 三角形最小路径和 | Python
-
【每日一道算法题】Leetcode之longest-increasing-path-in-a-matrix矩阵中的最长递增路径问题 Java dfs+记忆化
-
#leetcode刷题之路40-组合总和 II
-
荐 LeetCode 112. 路径总和 | Python
-
动态规划_leetcode.64.最小路径和
-
LeetCode 63. 不同路径 II
-
[leetcode]63. 不同路径 II
-
LeetCode——63.不同路径 II
-
leetcode——62不同路径