/113. Path Sum II

113. Path Sum II

Medium
Backtracking61.9% acceptance

Given the root node of a binary tree (as a TreeNode object) and an integer sum_value, return all root-to-leaf paths where the sum of the node values in the path 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: TreeNode(3, TreeNode(1), TreeNode(5, TreeNode(4), TreeNode(6))), 8

Output: [[3,5]]

Explanation: Only one path [3,5] sums to 8.

Example 2

Input: TreeNode(2, TreeNode(-1), TreeNode(3)), 2

Output: [[2,-1,1]]

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

Example 3

Input: TreeNode(10, TreeNode(5, TreeNode(2), TreeNode(7)), TreeNode(-3, None, TreeNode(11))), 22

Output: [[10,-3,11]]

Explanation: Only one path [10,-3,11] sums to 22.

Constraints

  • The number of nodes in the tree is in the range [0, 5000].
  • -1000 <= TreeNode.val <= 1000
  • -1000 <= sum_value <= 1000
Python (current runtime)

Case 1

Input: TreeNode(7, TreeNode(2), TreeNode(9, TreeNode(8), None)), 17

Expected: [[7,9,8]]

Case 2

Input: TreeNode(4, TreeNode(3, TreeNode(1)), TreeNode(5)), 8

Expected: [[4,3,1]]

Case 3

Input: TreeNode(1, TreeNode(2), TreeNode(3)), 4

Expected: []

Case 4

Input: TreeNode(0, TreeNode(-1), TreeNode(1)), 0

Expected: [[0,-1,1]]