网站关键词优化怎么弄,注册个网站多少钱,京东官网登录,怎样写网站描述112. 路径总和 - 力扣#xff08;LeetCode#xff09;
题目描述
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径#xff0c;这条路径上所有节点值相加等于目标和 targetSum 。如果存在#xff0c;返回 true LeetCode
题目描述
给你二叉树的根节点 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
解释由于树是空的所以不存在根节点到叶子节点的路径。提示
树中节点的数目在范围 [0, 5000] 内-1000 Node.val 1000-1000 targetSum 1000 代码
解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 backing(TreeNode* root,int targetSum,int curSum){curSumroot-val;if(!root-left !root-right){if(curSumtargetSum) return true;else return false;}bool leftPathfalse,rightPathfalse;if(root-left)leftPathbacking(root-left,targetSum,curSum);if(root-right)rightPathbacking(root-right,targetSum,curSum);return leftPath||rightPath;}bool hasPathSum(TreeNode* root, int targetSum) {if(!root) return false;return backing(root,targetSum,0);}
};
解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 backing(TreeNode* root,int cursum){if(!root-left !root-right cursum0) return true;if(!root-left !root-right) return false;if(root-left){if(backing(root-left,cursum-root-left-val))return true;}if(root-right){if(backing(root-right,cursum-root-right-val))return true;}return false;}bool hasPathSum(TreeNode* root, int targetSum) {if(!root) return false;return backing(root,targetSum-root-val);}
};
