/113. Path Sum II

113. Path Sum II

Medium
Backtracking61.9% acceptance

Given a binary tree represented as a list in level-order traversal (with None for missing nodes), and an integer sum_value, return all root-to-leaf paths where the sum of node values equals sum_value. Each path should be returned as a list of node values. A root-to-leaf path starts at the root and ends at a leaf node (a node with no children).

Example 1

Input: [[10,5,-3,3,2,None,11,3,-2,None,1], 18]

Output: [[10,5,2,1],[10,-3,11]]

Explanation: Paths: 10->5->2->1 and 10->-3->11 sum to 18.

Example 2

Input: [[7,2,5,None,None,4,6], 13]

Output: [[7,5,1]]

Explanation: Only path 7->5->1 sums to 13.

Example 3

Input: [[1,None,2,None,3,None,4], 10]

Output: []

Explanation: No root-to-leaf path sums to 10.

Constraints

  • The number of nodes in the tree is in the range [0, 5000].
  • -1000 <= node value <= 1000.
  • -1000 <= sum_value <= 1000.
  • Input tree is given as a level-order list with None for missing children.
Python (current runtime)

Case 1

Input: [[3,9,20,None,None,15,7], 42]

Expected: []

Case 2

Input: [[2,3,4,5,None,None,1], 10]

Expected: [[2,4,1]]

Case 3

Input: [[5,4,8,11,None,13,4,7,2,None,None,5,1], 27]

Expected: [[5,8,4,10]]