תיאור השאלה
You are given the root of a binary search tree in which the values of exactly two nodes were swapped by mistake. Recover the tree without changing its structure.
איך פותרים?
מעבר inorder על BST תקין נותן רצף ממוין. מחפשים את המקומות שבהם הרצף יורד: הצומת הראשון השגוי הוא הקודם בירידה הראשונה, והשני הוא הנוכחי בירידה האחרונה. בסוף מחליפים את הערכים שלהם. סיבוכיות: O(n).
פתרון קוד
JavaScript
Python
function recoverTree(root) {
let first = null;
let second = null;
let prev = null;
function inorder(node) {
if (!node) return;
inorder(node.left);
if (prev && prev.val > node.val) {
if (!first) first = prev;
second = node;
}
prev = node;
inorder(node.right);
}
inorder(root);
[first.val, second.val] = [second.val, first.val];
}
לעבור את ראיון העבודה הבא שלך בהצלחה
קורס דיגיטלי מקיף עם +25 שיעורים מעשיים, כשעתיים של וידאו, וליווי של מראיין בכיר.