문제 링크

Account Login - LeetCode

문제 풀이

트리를 순회하여 지나간 node의 sum을 구하여 targetSum 과 일치하면 고른 node들을 answer 에 넣는다.

나의 코드

var pathSum = function (root, targetSum) {
  const answer = [];
  function solve(arr, sum, pick) {
    if (!arr || arr.val === null) return;
    if (arr.left === null && arr.right === null) {
      if (sum + arr.val === targetSum) answer.push([...pick, arr.val]);
      return;
    }
    solve(arr.left, sum + arr.val, [...pick, arr.val]);
    solve(arr.right, sum + arr.val, [...pick, arr.val]);
  }
  solve(root, 0, []);
  return answer;
};

처음에 LeetCode에 익숙치 않아서 root가 배열로 들어오는 줄알고 tree를 배열로 변환하여 푸는 이상한 짓을 했지만 나름 도움이 됐다.

배열로 풀이한 코드

var pathSum = function (root, targetSum) {
  let answer = [];
  const tree = [0, root[0]];
  const visit = {};
  for (let i = 1, j = 2; i < root.length; ++j) {
    if (tree[Math.floor(j / 2)] != null) tree.push(root[i++]);
    else tree.push(null);
  }
  function dfs(idx, pick, sum) {
    if (tree[idx] === null) return;
    if (idx >= tree.length) {
      if (sum === targetSum && !visit[pick]) {
        answer.push([...pick]);
        visit[pick] = 1;
      }
      return;
    }
    dfs(idx * 2, [...pick, tree[idx]], sum + tree[idx]);
    dfs(idx * 2 + 1, [...pick, tree[idx]], sum + tree[idx]);
  }
  dfs(1, [], 0);
  return answer;
};