Show problems as
Classic problem #112EasyTreeDepth-First SearchBreadth-First SearchBinary Tree

Path Sum

Real-world version: A Branch Whose Loads Add Up
Tracked in this browser only
Read Path Sum on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstRecursive Search · Recursion, animated step by step

A rig hangs from a single top joint, and every joint carries at most two joints below it, held in a first slot and a second slot; either slot may be empty. Each joint carries a load, which may be negative.

The rig arrives as the flat list root, written level by level. root[0] is the top joint's load. Reading the list from left to right, every entry that is not null claims the next two unused positions as its first and second slot in that order, and null marks an empty slot. An entry that is null claims no positions of its own. If the list ends early, the slots that were never written are empty. An empty list means the rig has no joints at all.

A branch runs from the top joint down to a joint with both slots empty. Return true when some branch's loads add up to exactly targetSum.

Examples

Example 1

Input
root = [7, 4, 9, 2, null, null, 5], targetSum = 13
Output
true

The branch running 7, 4, 2 adds up to 13. The other branch runs 7, 9, 5, which comes to 21.

Example 2

Input
root = [1, 2, null], targetSum = 3
Output
true

The only branch runs 1 then 2, adding to 3. Note the top joint is not itself the end of a branch, since one of its slots is filled.

Example 3

Input
root = [], targetSum = 5
Output
false

The rig has no joints, so it has no branches and nothing can add up.

Constraints

  • The rig holds between 0 and 5000 joints.
  • 0 <= root.length <= 15000
  • -1000 <= root[i] <= 1000
  • -1000 <= targetSum <= 1000
  • root[0] is not null when the list is not empty.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def has_path_sum(root: list, targetSum: int) -> bool:
Java
public boolean hasPathSum(Integer[] root, int targetSum)

More on the same topics