leetcode-javascript/solutions/0113-path-sum-ii.js at development · Anuj9826/leetcode-javascript · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Path Sum II
 * Time Complexity: O(N * D)
 * Space Complexity: O(N * D)
 */
var pathSum = function (root, targetSum) {
  if (!root) {
    return [];
  }

  const allFoundPaths = [];
  const currentPathSegment = [];

  function exploreTreeDfs(currentNodeElement, remainingTargetValue) {
    if (!currentNodeElement) {
      return;
    }

    const nodeNumericalValue = currentNodeElement.val;
    currentPathSegment.push(nodeNumericalValue);
    const updatedTarget = remainingTargetValue - nodeNumericalValue;

    if (
      !currentNodeElement.left &&
      !currentNodeElement.right &&
      updatedTarget === 0
    ) {
      allFoundPaths.push([...currentPathSegment]);
    }

    if (currentNodeElement.left) {
      exploreTreeDfs(currentNodeElement.left, updatedTarget);
    }

    if (currentNodeElement.right) {
      exploreTreeDfs(currentNodeElement.right, updatedTarget);
    }

    currentPathSegment.pop();
  }

  exploreTreeDfs(root, targetSum);

  return allFoundPaths;
};