Does a Root-to-Leaf Path Sum to Target

easy tree dfs recursion

Problem

Given the root of a binary tree and a target sum, decide whether any root-to-leaf path sums exactly to the target. A leaf is a node with no children.

Carry the running total down the recursion. At a leaf, check whether the remaining target equals the leaf's value. The recursive form is hasPath(node, t) = hasPath(left, t − node.val) ∨ hasPath(right, t − node.val).

Inputtree: [5, 4, 8, 11, _, 13, 4, 7, 2], target: 22

Outputtrue

Path 5 → 4 → 11 → 2 sums to 22.

level-order ('_' for null)

target

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

function hasPathSum(root, target) {
  if (!root) return false;
  if (!root.left && !root.right) return target === root.val;
  const rem = target - root.val;
  return hasPathSum(root.left, rem) || hasPathSum(root.right, rem);
}

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

bool hasPathSum(TreeNode* root, int target) {
    if (!root) return false;
    if (!root->left && !root->right) return target == root->val;
    int rem = target - root->val;
    return hasPathSum(root->left, rem) || hasPathSum(root->right, rem);
}

Time: O(n) Space: O(h) recursion depth