力扣112. 路径总和

这一题仍然是遍历二叉树，要注意必须到叶子节点才比较看路径和是不是等于目标和。
因此我们需要判断是不是叶子节点。

 if(root->left==nullptr&&root->right==nullptr){       if(cursum==targetSum){flag=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:int flag;void dfs(TreeNode* root,int targetSum,int cursum){if(root==nullptr){return ;}else{if(root->left==nullptr&&root->right==nullptr){       if(cursum==targetSum){flag=1;}}if(root->left!=nullptr)dfs(root->left,targetSum,cursum+root->left->val);if(root->right!=nullptr)dfs(root->right,targetSum,cursum+root->right->val);}}bool hasPathSum(TreeNode* root, int targetSum) {int cursum=0;if(root==nullptr){return false;}dfs(root,targetSum,0+root->val);if(flag==1){return true;}else{return false;}}
};

时间复杂度O(n)