תיאור השאלה
Given a binary tree, find its minimum depth: the number of nodes along the shortest path from the root down to the nearest leaf. A leaf is a node with no children.
איך פותרים?
BFS לפי רמות: העלה הראשון שפוגשים נמצא בעומק המינימלי, ואפשר לעצור מיד. זה עדיף על רקורסיה פשוטה, שבה צריך להיזהר מצומת עם בן אחד בלבד (הוא לא עלה). סיבוכיות: O(n).
פתרון קוד
JavaScript
Python
function minDepth(root) {
if (!root) return 0;
let queue = [root];
let depth = 1;
while (queue.length) {
const next = [];
for (const node of queue) {
if (!node.left && !node.right) return depth;
if (node.left) next.push(node.left);
if (node.right) next.push(node.right);
}
queue = next;
depth++;
}
return depth;
}
לעבור את ראיון העבודה הבא שלך בהצלחה
קורס דיגיטלי מקיף עם +25 שיעורים מעשיים, כשעתיים של וידאו, וליווי של מראיין בכיר.