תיאור השאלה
Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values equals targetSum. Each path is returned as a list of node values.
איך פותרים?
DFS עם backtracking: מוסיפים כל צומת למסלול הנוכחי ומחסירים את ערכו מהיעד. בעלה שבו היעד מתאפס שומרים עותק של המסלול. ביציאה מהצומת מוציאים אותו מהמסלול. סיבוכיות: O(n²) במקרה הגרוע בגלל העתקת המסלולים.
פתרון קוד
JavaScript
Python
function pathSum(root, targetSum) {
const result = [];
const path = [];
function dfs(node, remaining) {
if (!node) return;
path.push(node.val);
remaining -= node.val;
if (!node.left && !node.right && remaining === 0) {
result.push([...path]);
} else {
dfs(node.left, remaining);
dfs(node.right, remaining);
}
path.pop();
}
dfs(root, targetSum);
return result;
}
לעבור את ראיון העבודה הבא שלך בהצלחה
קורס דיגיטלי מקיף עם +25 שיעורים מעשיים, כשעתיים של וידאו, וליווי של מראיין בכיר.