תיאור השאלה
Given the root of a binary tree, determine whether it is a valid binary search tree: every node's left subtree contains only values smaller than the node, every right subtree contains only values greater than the node, and both subtrees are themselves valid BSTs.
איך פותרים?
הטעות הנפוצה היא לבדוק רק את הבנים הישירים. במקום זה מעבירים בכל קריאה רקורסיבית טווח מותר (min, max): בירידה שמאלה הגבול העליון הופך לערך הצומת, ובירידה ימינה הגבול התחתון. סיבוכיות: O(n).
פתרון קוד
JavaScript
Python
function isValidBST(root, min = -Infinity, max = Infinity) {
if (!root) return true;
if (root.val <= min || root.val >= max) return false;
return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
}
לעבור את ראיון העבודה הבא שלך בהצלחה
קורס דיגיטלי מקיף עם +25 שיעורים מעשיים, כשעתיים של וידאו, וליווי של מראיין בכיר.