一、题目描述
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
示例 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
示例 3： 输入：root = [1,2], targetSum = 0 输出：false
提示： 树中节点的数目在范围 [0, 5000] 内 -1000 <= Node.val <= 1000 -1000 <= targetSum <= 1000
二、解题思路
利用 DFS 找出从根节点到叶子节点的所有路径，只要有任意一条路径的 和 等于 sum，就返回 True。
三、代码
代码语言：javascript复制/**
* 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 rs=false;
bool hasPathSum(TreeNode* root, int targetSum) {
travel(root,0,targetSum);
return rs;
}
void travel(TreeNode* root,int sum, int targetSum){
if(root==nullptr){
return;
}else{
sum =root->val;
}
cout<<sum<<endl;
if(targetSum==sum&&root->left==nullptr&&root->right==nullptr){
rs=true;
}
travel(root->left,sum,targetSum);
travel(root->right,sum,targetSum);
}
};四、复杂度分析
时间复杂度：O(N)，其中 N 是树的节点数。对每个节点访问一次。
空间复杂度：O(H)，其中 H 是树的高度。空间复杂度主要取决于递归时栈空间的开销，最坏情况下，树呈现链状，空间复杂度为 O(N)。平均情况下树的高度与节点数的对数正相关，空间复杂度为 O(logN)。
