All Leaf Paths With a Given Total

Medium

You are given the root root of a binary tree and an integer total. Find every root-to-leaf path whose node values add up to total. Return each path as the list of its node values from the root down to the leaf. A leaf is a node with no children. The paths themselves may be listed in any order; if none fit, return an empty list.

Example 1

root=tree_node([4, 2, 7, 1, 5, None, -2]), total=9 → [[4, 7, -2]]

There are three root-to-leaf paths: 4 → 2 → 1 (sum 7), 4 → 2 → 5 (11) and 4 → 7 → -2 (9). Only the last one fits.

Example 2

root=tree_node([1, 2, 2, 3, None, None, 3]), total=6 → [[1, 2, 3], [1, 2, 3]]

Both branches 1 → 2 → 3 sum to 6. The values match, but these are different paths, and both must be returned.

Example 3

root=tree_node([3, 1]), total=3 → []

The root 3 is not a leaf because it has a child. The only path 3 → 1 sums to 4, so the answer is empty.

Constraints

The tree has 0 to 5000 nodes
-1000 ≤ node value ≤ 1000
-1000 ≤ total ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Backtracking Binary Tree

Similar problems

Smallest Leaf-to-Root Word Medium Routes from Root to Leaves Easy Is It a Search Tree? Medium Two Mixed-Up Nodes Medium Tree Into a Right Chain Medium

Input

root=tree_node([4, 2, 7, 1, 5, None, -2]), total=9

Expected

[[4, 7, -2]]

Run checks the first 3 tests in your browser. Submit checks all 42 tests on the server, hidden ones included.