All problems

Path Sum

Easy · tree dfs

You are given the root of a binary tree and an integer target_sum.

A leaf is a node with no children. A root-to-leaf path starts at the root, moves down from a node to one of its children at each step, and stops at a leaf. The sum of a path is the total of the values of all the nodes on it, including the root and the leaf.

Return true if at least one root-to-leaf path has a sum equal to target_sum, otherwise false. A path that stops at a node that still has a child does not count. An empty tree has no paths, so it returns false.

Examples

Example 1

Input: root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1], target_sum = 22

Output: true

The path 5 -> 4 -> 11 -> 2 ends at a leaf and adds up to 22.

Example 2

Input: root = [1, 2, 3], target_sum = 5

Output: false

The two paths are 1 -> 2 (sum 3) and 1 -> 3 (sum 4).

Example 3

Input: root = [1, 2], target_sum = 1

Output: false

The root alone adds up to 1, but it is not a leaf because it has a child, so that path does not count.

Constraints