Symmetric Tree
ניתן לך עץ בינארי המאוחסן במערך tree לפי סדר שכבות. השורש נמצא באינדקס 0, הילדים של הצומת באינדקס i נמצאים באינדקסים 2*i+1 (שמאל) ו-2*i+2 (ימין), -1 מציין מקום ריק, והמערך עשוי להסתיים בערכי -1 נוספים. החזר true אם העץ הוא תמונת מראה של עצמו ביחס לקו אנכי העובר דרך השורש, ו-false אחרת. גם המבנה וגם הערכים חייבים להתאים.
פונקציה
- treeinteger-array
- עץ בינארי לפי סדר רמות, כאשר -1 מציין מקום ריק
- מחזירהboolean
- true אם העץ הוא תמונת ראי של עצמו, אחרת false
אילוצים
1 ≤ tree.length ≤ 32767- כל
tree[i]הוא-1או ערך המקיים0 ≤ tree[i] ≤ 1000. tree[0]לעולם אינו-1, לכן יש לעץ לפחות צומת אחד.- המערך עשוי להסתיים בערכי
-1נוספים אחרי הצומת האחרון. - שני הילדים של מקום ריק גם הם ריקים, והעומק הוא לכל היותר
14.
דוגמאות
- קלט
- tree = [1, 2, 2, 3, 4, 4, 3]
- פלט
- true
- הסבר
- קפלו את העץ לשניים. שני ערכי ה־
2באינדקסים1ו־2נפגשים, ערכי ה־3החיצוניים באינדקסים3ו־6נפגשים, וערכי ה־4הפנימיים באינדקסים4ו־5נפגשים.
- קלט
- tree = [1, 2, 2, -1, 3, -1, 3]
- פלט
- false
- הסבר
- שני מופעי
3תלויים מימין להורים שלהם. בתמונת מראה, הילד הימני של ה־2השמאלי (אינדקס4) צריך לפנות אל הילד השמאלי של ה־2הימני (אינדקס5), ואינדקס5ריק.
- קלט
- tree = [4, 6, 6, 5, -1, -1, 9]
- פלט
- false
- הסבר
- הצורה היא תמונת מראה: האינדקס
3פונה אל האינדקס6, ובשניהם יש צומת. הערכים שלהם שונים,5לעומת9, ולכן העץ אינו סימטרי.
+16 בדיקות נסתרות בשליחה
שאלת המשך
אם הצורה משקפת את עצמה, אבל חלק מהערכים לא, מהו המספר הקטן ביותר של ערכי צמתים שעליך לשנות כדי להפוך את העץ לסימטרי?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
לאיזה צומת הילד השמאלי של השורש צריך להתאים? ולאיזה צומת הילד השמאלי של אותו צומת צריך להתאים?
השוו בין שני צמתים בכל פעם. הם משקפים זה את זה כאשר שניהם ריקים, או כאשר שניהם מכילים אותו ערך והילדים מתחלפים: הילד השמאלי של אחד משקף את הילד הימני של האחר, והילד הימני של אחד משקף את הילד השמאלי של האחר.
שמור מחסנית של זוגות אינדקסים, החל מ־
(1, 2). שלוף זוג: דלג עליו אם שני המקומות ריקים, החזר כישלון אם רק אחד מהם ריק או שהערכים שונים, אחרת דחוף את(2*a+1, 2*b+2)ואת(2*a+2, 2*b+1).
פתרון
סימטריה היא תכונה של זוגות. לכל צומת יש בן זוג במיקום המשוקף בצד השני של השורש, ובן הזוג של ילד שמאלי הוא ילד ימני. לכן לעולם לא משווים צומת לילדים שלו: עוברים בשני חצאי העץ בכיוונים מנוגדים בו־זמנית, משווים את המבנה ואת הערך בכל זוג, ועוצרים בזוג הראשון שבו יש אי־התאמה.
השווה כל רמה להיפוכה
האינטואיציה
ראשית, איך נעים במערך. לצומת שבאינדקס i יש בן שמאלי באינדקס 2*i+1 ובן ימני באינדקס 2*i+2. בן נחשב ממשי רק אם האינדקס שלו נמצא בתוך המערך והערך שם אינו -1. במערך [1, 2, 2, 3, 4, 4, 3], לשורש 1 יש בנים באינדקסים 1 ו-2, ול-2 שבאינדקס 1 יש בנים באינדקסים 3 ו-4.
עכשיו נתבונן בעץ רמה אחת בכל פעם. תמונת מראה נקראת אותו הדבר משמאל לימין ומימין לשמאל, ולכן בכל רמה, כשכותבים אותה יחד עם המקומות הריקים שלה, חייב להתקבל אותו הדבר בשני הכיוונים. בדוגמה הראשונה, הרמות שמתחת לשורש הן 2 2 ו-3 4 4 3. בדוגמה השנייה הן 2 2, ואחריהן -1 3 -1 3, שהפוכה נקראת 3 -1 3 -1, ולכן התשובה היא false.
המקומות הריקים חייבים להישאר בשורה. בלעדיהם, הרמה התחתונה בדוגמה השנייה הייתה נקראת 3 3 ועוברת את הבדיקה. כתבו ערך אחד עבור כל מקום של בן של כל צומת ממשי ברמה, -1 עבור מקום ריק; גם המקומות של הבנים של מקומות ריקים ריקים, ולכן הם לא מוסיפים דבר. מבקרים בכל צומת פעם אחת, ולכן זמן הריצה הוא O(n), ורמה אחת נשמרת בזיכרון בכל פעם, כלומר O(w) עבור הרמה הרחבה ביותר w.
אלגוריתם
- התחל ברשימה שמכילה את אינדקס השורש
0. - עבור כל אינדקס ברשימה, משמאל לימין, כתוב את שני המקומות של הילדים: את הערך של הילד אם הוא קיים, ו־
-1אם המקום ריק. אסוף את הילדים הקיימים לרמה הבאה. - אם שורת המקומות של הילדים שונה מהשורה ההפוכה שלה, החזר
false. - עבור לרמה הבאה וחזור על הפעולה עד שהיא ריקה, ואז החזר
true.
def isSymmetric(tree):
n = len(tree)
level = [0] # the real nodes of one level, left to right
while level:
row = [] # the child spots under this level, -1 for an empty one
next_level = []
for i in level:
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
row.append(tree[child])
next_level.append(child)
else:
row.append(-1)
if row != row[::-1]:
return False
level = next_level
return Trueרקורסיה על זוגות משתקפים
האינטואיציה
במקום להשוות רמות שלמות, משווים בין שתי תתי־העצים: תת־העץ השמאלי של השורש, שמתחיל באינדקס 1, ותת־העץ הימני שלו, שמתחיל באינדקס 2. שני מקומות הם תמונת ראי זה של זה כאשר שניהם ריקים, או כאשר בשניהם נמצא אותו ערך והילדים שלהם מצטלבים. הילד השמאלי של אחד מהם הוא תמונת ראי של הילד הימני של האחר (הזוג החיצוני), והילד הימני של אחד מהם הוא תמונת ראי של הילד השמאלי של האחר (הזוג הפנימי).
בדוגמה הראשונה, mirrors(1, 2) משווה בין שני ערכי ה־2, ואז קוראת ל־mirrors(3, 6) עבור ערכי ה־3 החיצוניים ול־mirrors(4, 5) עבור ערכי ה־4 הפנימיים. כל אחת מהקריאות האלה מוצאת רק מקומות ריקים בהמשך ומחזירה true. בדוגמה השנייה, mirrors(4, 5) מוצאת 3 באינדקס 4 מול מקום ריק באינדקס 5, מחזירה false, וה־false מטפס בחזרה למעלה.
כל צומת ממשי שייך לכל היותר לזוג אחד, ולכן זמן הריצה הוא O(n). עומק מחסנית הקריאות הוא כעומק העץ, O(h), שהוא לכל היותר 14 מסגרות כאן.
אלגוריתם
- כתבו
mirrors(a, b). מקום ריק אם האינדקס גדול מהאינדקס האחרון או אם הוא מכיל-1. אם שני המקומות ריקים, החזירוtrue; אם רק אחד מהם ריק, החזירוfalse. - אם
tree[a]ו-tree[b]שונים, החזירוfalse. - אחרת החזירו
mirrors(2*a+1, 2*b+2)וגםmirrors(2*a+2, 2*b+1). - החזירו
mirrors(1, 2). שורש ללא ילדים יוצר שני מקומות ריקים, ולכן התוצאה היאtrue.
def isSymmetric(tree):
n = len(tree)
def mirrors(a, b):
# Spots a and b must hold the same value, or both be empty.
empty_a = a >= n or tree[a] == -1
empty_b = b >= n or tree[b] == -1
if empty_a or empty_b:
return empty_a and empty_b
return (tree[a] == tree[b]
and mirrors(2 * a + 1, 2 * b + 2) # outer pair
and mirrors(2 * a + 2, 2 * b + 1)) # inner pair
return mirrors(1, 2)מחסנית מפורשת של זוגות סימטריים
האינטואיציה
הרקורסיה זקוקה לדבר אחד בלבד: זוגות שעדיין ממתינים לבדיקה. שמור את הזוגות האלה במחסנית משלך, וכך הקריאות ייעלמו. התחל בזוג (1, 2). שלוף זוג. אם שתי הנקודות ריקות, אין שום דבר מתחתיהן, אז ממשיכים הלאה. אם אחת מהן ריקה או שהערכים שונים, העץ אינו סימטרי. אחרת, דחוף למחסנית את הזוג החיצוני (2*a+1, 2*b+2) ואת הזוג הפנימי (2*a+2, 2*b+1).
סדר בדיקת הזוגות אינו משנה, כי העץ סימטרי רק אם כל זוג תואם. מחסנית מספקת סדר של חיפוש לעומק; תור היה מספק סדר לפי רמות ופועל באותה דרך. הדוגמה השלישית נעצרת בזוג הראשון שאינו תקין, (3, 6), שמכיל את 5 ואת 9.
כל שליפה מטפלת בזוג אחד, וכל צומת ממשי מופיע בזוג אחד לכל היותר, ולכן זמן הריצה הוא O(n). המחסנית שומרת בערך זוג אחד שממתין לטיפול עבור כל רמה בנתיב הנוכחי, כלומר צריכת מקום של O(h), ואין צורך לדאוג למגבלת הרקורסיה.
אלגוריתם
- דחוף את הזוג
(1, 2)למחסנית. - שלוף זוג
(a, b). אם שני המקומות ריקים (האינדקס מעבר לסוף או-1), המשך לזוג הבא. - אם רק מקום אחד ריק, או ש-
tree[a]שונה מ-tree[b], החזרfalse. - דחוף את
(2*a+1, 2*b+2)ואת(2*a+2, 2*b+1). - כשהמחסנית ריקה, החזר
true.
def isSymmetric(tree):
n = len(tree)
stack = [(1, 2)] # pairs of spots that must mirror each other
while stack:
a, b = stack.pop()
empty_a = a >= n or tree[a] == -1
empty_b = b >= n or tree[b] == -1
if empty_a and empty_b:
continue
if empty_a or empty_b or tree[a] != tree[b]:
return False
stack.append((2 * a + 1, 2 * b + 2)) # outer pair
stack.append((2 * a + 2, 2 * b + 1)) # inner pair
return True
מלכודות ומקרי קצה
רוב התשובות השגויות משוות בין זוג הצמתים הלא נכון, או שוכחות שמקום ריק הוא חלק מהצורה.
- בדיקת כל תת-עץ בפני עצמו. תת-העץ השמאלי לא חייב להיות סימטרי בפני עצמו: ב-
[1, 2, 2, 3, 4, 4, 3]תת-העץ2, 3, 4אינו סימטרי, והעץ כולו כן. הוא צריך להיות תמונת מראה של תת-העץ הימני. - התאמת הילדים בדרך הלא נכונה. הילד השמאלי של צד אחד נמצא מול הילד הימני של הצד השני:
(2*a+1, 2*b+2)ו-(2*a+2, 2*b+1), לעולם לא(2*a+1, 2*b+1). - השוואת ערכים בלבד. הסירו את המקומות הריקים מ-
[1, 2, 2, -1, 3, -1, 3]ובכל רמה נקבל אותה קריאה בשני הכיוונים, אך העץ אינו סימטרי. השאירו את-1בשורת הרמה, או בדקו אם המקום ריק בבדיקת הזוג. - קריאה מעבר לסוף. אינדקס שמעבר לסוף המערך הוא מקום ריק. בדקו
a < nלפני קריאתtree[a]; בעץ בעל צומת יחיד אין כלל אינדקס1או2. - עצירה בזוג הראשון שמתאים. זוג מתאים אחד אינו מוכיח דבר; החזירו
trueרק אחרי שכל הזוגות נבדקו. - בלבול בהיסט ב-Lua וב-R, שבהן מערכים מתחילים ב-1. השאירו את אינדקסי הצמתים מבוססי-0 עבור החישוב
2*i+1וקראו אתtree[i + 1].
שאלות נפוצות4
מהי סיבוכיות הזמן של עץ סימטרי?
כל צומת ממשי מושווה פעם אחת, כחלק מזוג מראה אחד, ולכן זמן הריצה הוא O(n). הגרסאות הרקורסיבית וזו שמשתמשת במחסנית צורכות שטח נוסף של O(h) עבור הזוגות הממתינים לאורך הנתיב הנוכחי. הגרסה שעובדת רמה אחר רמה שומרת רמה אחת בזיכרון, O(w) עבור הרמה הרחבה ביותר.
איך בודקים אם עץ בינארי הוא סימטרי ללא רקורסיה?
החזיקו מחסנית או תור של זוגות צמתים שצריכים לשקף זה את זה, החל משני הילדים של השורש. הוציאו זוג, נכשלו אם יש אי־התאמה, והוסיפו את הזוג החיצוני ואת הזוג הפנימי של ילדיהם. אם המחסנית מתרוקנת בלי שנמצאה אי־התאמה, העץ סימטרי.
מה ההבדל בין עץ סימטרי לשני עצים זהים?
שני עצים זהים כאשר משווים בין שמאל לשמאל ובין ימין לימין. עץ סימטרי כאשר תת-העץ השמאלי שלו זהה לתמונת המראה של תת-העץ הימני שלו, ולכן ההשוואה מתבצעת בהצלבה: שמאל מול ימין וימין מול שמאל. אותו קוד לבדיקת זוגות פותר את שתי הבעיות, כאשר זוגות הילדים מוחלפים.
האם עץ עם צומת יחיד הוא סימטרי?
כן. לצומת יחיד יש שני מקומות ריקים לילדים, ושני מקומות ריקים הם תמונת ראי זה של זה. שורש עם ילד אחד בדיוק לעולם אינו סימטרי, כי הילד פונה אל מקום ריק.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def isSymmetric(tree):
# כתבו כאן קודמקרה 1
מקרה 2
מקרה 3
קלט
tree = [1, 2, 2, 3, 4, 4, 3]
צפוי
true