Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
A leaf is a node with no children.
Example 1:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.
Example 2:
Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.
Example 3:Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.
Constraints:
The number of nodes in the tree is in the range [0, 5000].
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目大意：
判断树是否存在根节点到叶子节点权值等于目标值的情况。
实现思路：
递归，每一次递归目标值减去当前结点的权值，等到达叶子结点的时候判断目标值是否已经减到了
0。
实现代码：
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if(root==NULL) return false;
if(root) targetSum-=root->val;
if(root&&root->left==NULL&&root->right==NULL){
if(targetSum==0) return true;
else return false;
}
return hasPathSum(root->left,targetSum)||hasPathSum(root->right,targetSum);
}
};还有一种解法我觉得很厉害。
就是用队列记录下每一次的结点和结点对应的总值，判断是否等于目标值。
下面先附上python代码，相对比较好理解。
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root:
return False
que = collections.deque()
que.append((root, root.val))
while que:
node, path = que.popleft()
if not node.left and not node.right and path == sum:
return True
if node.left:
que.append((node.left, path + node.left.val))
if node.right:
que.append((node.right, path + node.right.val))
return False
作者：fuxuemingzhu
链接：https://leetcode-cn.com/problems/path-sum/solution/lu-jing-zong-he-de-si-chong-jie-fa-dfs-hui-su-bfs-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。还有用堆栈实现的：
class Solution(object):
def hasPathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
"""
if not root:
return False
stack = []
stack.append((root, root.val))
while stack:
node, path = stack.pop()
if not node.left and not node.right and path == sum:
return True
if node.left:
stack.append((node.left, path + node.left.val))
if node.right:
stack.append((node.right, path + node.right.val))
return False
作者：fuxuemingzhu
链接：https://leetcode-cn.com/problems/path-sum/solution/lu-jing-zong-he-de-si-chong-jie-fa-dfs-hui-su-bfs-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。我觉得队列和堆栈比起来，其实差不多，都是用来存储结点的值，然后一个一个弹出，往下遍历。应该都是bfs
接下来是官方的bfs版本（c++），对于c++来说，他的堆栈或是队列只能存储一个值，所以官方的答案里运用了两个队列，分别存储结点和到该结点的总权值。
class Solution {
public:
bool hasPathSum(TreeNode *root, int sum) {
if (root == nullptr) {
return false;
}
queue<TreeNode *> que_node;
queue<int> que_val;
que_node.push(root);
que_val.push(root->val);
while (!que_node.empty()) {
TreeNode *now = que_node.front();
int temp = que_val.front();
que_node.pop();
que_val.pop();
if (now->left == nullptr && now->right == nullptr) {
if (temp == sum) {
return true;
}
continue;
}
if (now->left != nullptr) {
que_node.push(now->left);
que_val.push(now->left->val + temp);
}
if (now->right != nullptr) {
que_node.push(now->right);
que_val.push(now->right->val + temp);
}
}
return false;
}
};
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/path-sum/solution/lu-jing-zong-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。通过这道题，我首先练习了递归，然后又学到了bfs的方法(用堆栈或队列存储数值)