Path Sum

Easy

Python

def has_path_sum(root,target):
    if not root: return False
    if not root.left and not root.right: return root.val==target
    return has_path_sum(root.left,target-root.val) or has_path_sum(root.right,target-root.val)

Java

public boolean hasPathSum(TreeNode root,int target){
    if(root==null) return false;
    if(root.left==null&&root.right==null) return root.val==target;
    return hasPathSum(root.left,target-root.val)||hasPathSum(root.right,target-root.val);
}

Key Insight

Subtract as you go. Python truthiness vs null. 'or' vs '||'.

Python → Java Differences

'not root' vs ==null
'or' vs '||'
Subtract and check identical

Python

def has_path_sum(root,target):
    if not root: return False
    if not root.left and not root.right: return root.val==target
    return has_path_sum(root.left,target-root.val) or has_path_sum(root.right,target-root.val)

Java

public boolean hasPathSum(TreeNode root,int target){
    if(root==null) return false;
    if(root.left==null&&root.right==null) return root.val==target;
    return hasPathSum(root.left,target-root.val)||hasPathSum(root.right,target-root.val);
}

Algorithm Steps

1. Null: false
2. Leaf: check remaining
3. Recurse subtracting val

← Previous All Trees Next →