תיאור השאלה
Given a binary tree (not necessarily perfect), populate each node's next pointer to point to its next right node on the same level, or null if there is none.
איך פותרים?
עוברים על כל רמה דרך מצביעי next שכבר חיברנו, ובונים את הרמה הבאה בעזרת צומת דמה ומצביע tail: כל בן שקיים מתחברים אליו מה־tail ומקדמים אותו. בסוף הרמה, dummy.next הוא תחילת הרמה הבאה. סיבוכיות: O(n) זמן, O(1) זיכרון.
פתרון קוד
JavaScript
Python
function connect(root) {
let head = root;
while (head) {
const dummy = { next: null };
let tail = dummy;
for (let node = head; node; node = node.next) {
if (node.left) {
tail.next = node.left;
tail = tail.next;
}
if (node.right) {
tail.next = node.right;
tail = tail.next;
}
}
head = dummy.next;
}
return root;
}
לעבור את ראיון העבודה הבא שלך בהצלחה
קורס דיגיטלי מקיף עם +25 שיעורים מעשיים, כשעתיים של וידאו, וליווי של מראיין בכיר.