תיאור השאלה
Given the head of a singly linked list whose elements are sorted in ascending order, convert it to a height-balanced binary search tree.
איך פותרים?
טריק ה־inorder: סופרים את אורך הרשימה, ובונים את העץ ברקורסיה על טווח אינדקסים. קודם בונים את תת־העץ השמאלי, אז לוקחים את הצומת הנוכחי ברשימה כשורש ומתקדמים, ואז בונים את הימני. כך עוברים על הרשימה פעם אחת בלבד. סיבוכיות: O(n).
פתרון קוד
JavaScript
Python
function sortedListToBST(head) {
let length = 0;
for (let node = head; node; node = node.next) length++;
let current = head;
function build(left, right) {
if (left > right) return null;
const mid = Math.floor((left + right) / 2);
const leftTree = build(left, mid - 1);
const root = new TreeNode(current.val);
current = current.next;
root.left = leftTree;
root.right = build(mid + 1, right);
return root;
}
return build(0, length - 1);
}
לעבור את ראיון העבודה הבא שלך בהצלחה
קורס דיגיטלי מקיף עם +25 שיעורים מעשיים, כשעתיים של וידאו, וליווי של מראיין בכיר.