112. 路径总和
给你二叉树的根节点 root
和一个表示目标和的整数 targetSum
。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum
。如果存在,返回 true
;否则,返回 false
。
叶子节点 是指没有子节点的节点。
示例 1:
![](https://assets.leetcode.com/uploads/2021/01/18/pathsum1.jpg)
输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出:true
解释:等于目标和的根节点到叶节点路径如上图所示。
示例 2:
![](https://assets.leetcode.com/uploads/2021/01/18/pathsum2.jpg)
输入: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
题解
使用递归求解,注意必须根节点到叶子节点
查看代码
/**
* 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 res=false;
void work(TreeNode* cur, int& targetSum,int curSum){//curSum记录当前和
if(curSum==targetSum&&cur->left==NULL&&cur->right==NULL){//相等且是叶子节点
res=true;
return;
}
if(cur->left)//因为val有负数,所以没办法剪枝
work(cur->left,targetSum,curSum+cur->left->val);
if(cur->right)
work(cur->right,targetSum,curSum+cur->right->val);
}
bool hasPathSum(TreeNode* root, int targetSum) {
if(root==NULL)
return res;
work(root,targetSum,root->val);
return res;
}
};