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
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
def dfs(root, sum):
if root is None:
return False
if root.val == sum and root.left is None and root.right is None:
return True
return dfs(root.left, sum - root.val) or dfs(root.right, sum - root.val)
return dfs(root, sum)/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
return dfs(root, sum);
}
private boolean dfs(TreeNode root, int sum) {
if (root == null) return false;
if (root.val == sum && root.left == null && root.right == null) return true;
return dfs(root.left, sum - root.val) || dfs(root.right, sum - root.val);
}
}class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if (root == NULL) return false;
if (root->right == NULL && root->left == NULL && sum == root->val) return true;
bool leftTrue = hasPathSum(root->left, sum - root->val);
bool rightTrue = hasPathSum(root->right, sum - root->val);
return (leftTrue || rightTrue);
}
};/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
if (root == null) {
return false;
}
const { val, left, right } = root;
if (left == null && right == null) {
return targetSum - val === 0;
}
return (
hasPathSum(left, targetSum - val) || hasPathSum(right, targetSum - val)
);
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
pub fn has_path_sum(root: Option<Rc<RefCell<TreeNode>>>, target_sum: i32) -> bool {
match root {
None => false,
Some(node) => {
let mut node = node.borrow_mut();
// 确定叶结点身份
if node.left.is_none() && node.right.is_none() {
return target_sum - node.val == 0;
}
let val = node.val;
Self::has_path_sum(node.left.take(), target_sum - val)
|| Self::has_path_sum(node.right.take(), target_sum - val)
}
}
}
}