תיאור השאלה
Given the root of a binary tree, flatten it in place into a "linked list": every node's right pointer points to the next node in preorder, and every left pointer is null.
איך פותרים?
לכל צומת עם בן שמאלי: מוצאים את הצומת הימני ביותר בתת־העץ השמאלי, מחברים אליו את תת־העץ הימני, מעבירים את השמאלי לימין ומאפסים את השמאלי. ממשיכים ימינה. זה עובד בלי רקורסיה ובלי זיכרון נוסף. סיבוכיות: O(n) זמן, O(1) זיכרון.
פתרון קוד
JavaScript
Python
function flatten(root) {
let node = root;
while (node) {
if (node.left) {
let rightmost = node.left;
while (rightmost.right) rightmost = rightmost.right;
rightmost.right = node.right;
node.right = node.left;
node.left = null;
}
node = node.right;
}
}
לעבור את ראיון העבודה הבא שלך בהצלחה
קורס דיגיטלי מקיף עם +25 שיעורים מעשיים, כשעתיים של וידאו, וליווי של מראיין בכיר.