[LeetCode] 113. Path Sum II

문제 출처: https://leetcode.com/problems/path-sum-ii/

Path Sum II - LeetCode

 

문제

이진트리의 root 와 정수 targetSum 이 주어지면, 루트에서 리프까지 경로의 합이 targetSum인 모든 경로를 반환하라.

 

리프는 자식이 없는 노드이다.

예제

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

Input: root = [1,2,3], targetSum = 5
Output: []

Input: root = [1,2], targetSum = 0
Output: []

풀이

DFS를 이용하여 문제를 풀 수 있다.

 

DFS 방식으로 루트부터 리프 노드까지의 경로를 찾아간다. 경로를 탐색하면서 방문하는 노드들의 값을 합하고 리프 노드를 방문했을 때, targetSum과 비교하여 결과 리스트에 해당 경로를 추가할지 말지를 결정한다.

var pathSum = function(root, targetSum) {
  const ans = [];

  if (!root) { return ans; }

  var dfs = function(root, sum, path) {
    const pathSum = sum + root.val;
    const curPath = path.slice();
    curPath.push(root.val);

    if (root.left == null && root.right == null) {
        if (pathSum == targetSum) { ans.push(curPath); }
        return;
    }

    if (root.left) { dfs(root.left, pathSum, curPath); }
    if (root.right) { dfs(root.right, pathSum, curPath); }
  }

  dfs(root, 0, []);
  
  return ans;
};

 

Github: 113.js

GitHub - opwe37/Algorithm-Study