תיאור השאלה
Given a binary tree, determine whether it is height-balanced: for every node, the heights of its left and right subtrees differ by at most one.
איך פותרים?
פונקציה אחת שמחזירה את הגובה של תת־העץ, או 1- אם הוא כבר לא מאוזן. כך כל צומת נבדק פעם אחת ולא מחשבים גבהים שוב ושוב. סיבוכיות: O(n).
פתרון קוד
JavaScript
Python
function isBalanced(root) {
function height(node) {
if (!node) return 0;
const left = height(node.left);
if (left === -1) return -1;
const right = height(node.right);
if (right === -1 || Math.abs(left - right) > 1) return -1;
return 1 + Math.max(left, right);
}
return height(root) !== -1;
}
לעבור את ראיון העבודה הבא שלך בהצלחה
קורס דיגיטלי מקיף עם +25 שיעורים מעשיים, כשעתיים של וידאו, וליווי של מראיין בכיר.