【Leetcode】112. 路径总和(简单)
LeetCode 简单 路径 总和 112
2023-09-11 14:15:38 时间
一、题目
1、题目描述
给你二叉树的根节点 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
解释:由于树是空的,所以不存在根节点到叶子节点的路径。
2、基础框架
/**
* 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 hasPathSum(TreeNode* root, int targetSum) {
}
};
3、原题链接
二、解题报告
1、代码详解
/**
* 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 process(TreeNode *root, int rest) {
if (root->left == nullptr && root->right == nullptr)
return rest == root->val;
bool ans = root->left != nullptr ? process(root->left, rest - root->val) : false;
ans |= root->right != nullptr ? process(root->right, rest - root->val) : false;
return ans;
}
bool hasPathSum(TreeNode* root, int targetSum) {
if (root == nullptr) return false;
return process(root, targetSum);
}
};
或者计算访问过的节点的当前和,当孩子节点不为空时,才继续往下执行:
/**
* 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 isSum = false;
void process(TreeNode *root, int preSum, int sum) {
if (root->left == nullptr && root->right == nullptr) {
if (root->val + preSum == sum) {
isSum = true;
}
return ;
}
preSum += root->val;
if (root->left != nullptr) process(root->left, preSum, sum);
if (root->right != nullptr) process(root->right, preSum, sum);
}
bool hasPathSum(TreeNode* root, int targetSum) {
if (root == nullptr) return false;
isSum = false;
process(root, 0, targetSum);
return isSum;
}
};
相关文章
- Leetcode 之Balanced Binary Tree(49)
- Java实现 LeetCode 100 相同的树
- Java实现 LeetCode 2 两数相加
- 【数组&双指针】LeetCode 1. 两数之和【简单】
- leetcode 226. 翻转二叉树
- 【LeetCode Python实现】118. 杨辉三角(简单)
- 【LeetCode 简单 动态规划 python3】1025. 除数博弈
- 【LeetCode 简单 字符串】28 实现 strStr()
- 【LeetCode 简单 数组】35 搜索插入位置
- 【LeetCode Python实现】283.移动零(简单)
- 【LeetCode 简单 数组 python3】27. 移除元素
- 【LeetCode Python实现】26. 删除排序数组中的重复项(简单)
- 【LeetCode Python实现】225. 用队列实现栈(简单)
- LeetCode Pow(x, n)-简单粗暴法解决
- [LeetCode] Search in Rotated Sorted Array II [36]
- [LeetCode] Decode Ways [33]