文章目录
2.示例3.答案①递归②BFS③DFS给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
2.示例
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22输出：true解释：等于目标和的根节点到叶节点路径如上图所示。输入：root = [], targetSum = 0输出：false解释：由于树是空的，所以不存在根节点到叶子节点的路径。3.答案
①递归
注意第二个示例，当结点为空时认为不存在路径返回false;
可以使得参数 targetSum等于当前路径上为了凑出targetSum还差的数值。
停止条件:
结点为空时返回false, 当前结点为叶子结点且val=targetSum(刚好凑出targetSum) 返回true。
递归内容: 在左孩子上查找，在右孩子上查找
返回值: 左右孩子查找结果的或
bool hasPathSum(TreeNode* root, int targetSum) { //尝试递归，将taargetsum看做还差的值 if(!root) return false;//空指针,检查路径时，不能把节点为空当做一种 if(!root->left&&!root->right) return targetSum==root->val; //叶子结点，把这个当做递归的退出条件之一 return hasPathSum(root->left,targetSum-root->val)||hasPathSum(root->right,targetSum-root->val);②BFS
层次遍历中，可以一层一层检查，每次保存当前结点和当前路径所有节点和.
bool hasPathSum(TreeNode* root, int targetSum) { if(!root) return false;//空指针,检查路径时，不能把节点为空当做一种 queue<TreeNode*> qt; queue<int> qi; qt.push(root); qi.push(root->val); while(!qt.empty()){ TreeNode* tmp=qt.front(); //取出当前结点 qt.pop(); int val=qi.front(); //当前路径和 qi.pop(); if(!tmp->left&&!tmp->right) { //当前为叶子结点 if(targetSum==val) return true; continue; } if(tmp->left) qt.push(tmp->left),qi.push(val+tmp->left->val); if(tmp->right) qt.push(tmp->right),qi.push(val+tmp->right->val); } return false;③DFS
深度优先遍历同样，每次保存当前结点和当前结点路径和。
bool hasPathSum(TreeNode* root, int targetSum) { if(!root) return false; /深度优先 ,每次都是一条路径和 stack<TreeNode*> st; stack<int> si; st.push(root); si.push(root->val); while(!st.empty()){ TreeNode* tmp=st.top(); //取出当前结点 st.pop(); int val=si.top(); si.pop(); if(!tmp->left&&!tmp->right) { //当前为叶子结点 if(targetSum==val) return true; continue; } if(tmp->left) st.push(tmp->left),si.push(val+tmp->left->val); if(tmp->right) st.push(tmp->right),si.push(val+tmp->right->val); } return false; }来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/path-sum