CodeKata Path Sum II
문제 링크
문제 풀이
트리를 순회하여 지나간 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;
};
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;
};
Author And Source
이 문제에 관하여(CodeKata Path Sum II), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@coolchaeyoung/CodeKata-Path-Sum-II저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)