Simmetrik daraxt

Binar daraxt berilgan. U o'z o'qi (ildizi) atrofida simmetrik ekanligini aniqlang.

Simmetrik:          Simmetrik emas:
      [1]                 [1]
     /   \               /   \
   [2]   [2]           [2]   [2]
   / \ / \             \       \
 [3][4][4][3]          [3]     [3]

Daraxt simmetrik bo'lishi uchun u o'z ko'zgudagi aksiga teng bo'lishi kerak. Ya'ni: chap va o'ng kenja daraxtlar bir-birining ko'zgudagi aksi.

Asosiy g'oya: ikkita tugunni solishtirish

Bitta tugunni o'zi bilan solishtirish (ildiz o'qi simmetriyasi) rekursiv tarzda ikki tugunni solishtiruvchi funksiyaga aylanadi.

Ikki kenja daraxt simmetrik bo'lishi uchun: 1. Ikkalasining ildiz qiymatlari teng. 2. left.left va right.right simmetrik. 3. left.right va right.left simmetrik.

FUNCTION IS_MIRROR(left, right)
    IF left = NULL AND right = NULL
        RETURN TRUE        // ikkisi ham bo'sh → simmetrik

    IF left = NULL OR right = NULL
        RETURN FALSE       // bittasi bo'sh, ikkinchisi emas → asimmetrik

    IF left.value ≠ right.value
        RETURN FALSE       // qiymatlari teng emas → asimmetrik

    RETURN IS_MIRROR(left.left,  right.right) AND
           IS_MIRROR(left.right, right.left)

FUNCTION IS_SYMMETRIC(root)
    IF root = NULL
        RETURN TRUE

    RETURN IS_MIRROR(root.left, root.right)

Bosqichma-bosqich dry run

      [1]
     /   \
   [2]   [2]
   / \ / \
 [3][4][4][3]

IS_SYMMETRIC(1):
  IS_MIRROR(2, 2):
    2 = 2 ✓
    IS_MIRROR(2.left=3, 2.right=3):     ← tashqi juft
      3 = 3 ✓
      IS_MIRROR(NULL, NULL) = TRUE       ← ikkisi ham barg
      IS_MIRROR(NULL, NULL) = TRUE
      return TRUE
    IS_MIRROR(2.right=4, 2.left=4):     ← ichki juft
      4 = 4 ✓
      IS_MIRROR(NULL, NULL) = TRUE
      IS_MIRROR(NULL, NULL) = TRUE
      return TRUE
    return TRUE AND TRUE = TRUE
  return TRUE

Simmetrik emas holat:

      [1]
     /   \
   [2]   [2]
     \     \
     [3]   [3]

IS_MIRROR(2, 2):
  2 = 2 ✓
  IS_MIRROR(2.left=NULL, 2.right=3):
    left = NULL, right = 3 → RETURN FALSE

Javob: FALSE

Iterativ yondashuv: navbat bilan

Rekursiya o'rniga navbatga juft-juft solishtiriladigan tugunlar qo'shamiz.

FUNCTION IS_SYMMETRIC_BFS(root)
    IF root = NULL
        RETURN TRUE

    queue = [root.left, root.right]

    WHILE queue bo'sh emas
        left  = queue dan DEQUEUE
        right = queue dan DEQUEUE

        IF left = NULL AND right = NULL
            CONTINUE       // bu juft simmetrik, davom et

        IF left = NULL OR right = NULL
            RETURN FALSE

        IF left.value ≠ right.value
            RETURN FALSE

        // Keyingi solishtiriladigan juftlarni qo'sh
        queue ga left.left  ENQUEUE
        queue ga right.right ENQUEUE

        queue ga left.right ENQUEUE
        queue ga right.left ENQUEUE

    RETURN TRUE

Navbatda har doim juft-juft element bo'ladi: biri chapdan, biri o'ngdan. Ular "ko'zgudagi juft" sifatida solishtiriladi.

Dry run:

queue: [left=2, right=2]

Iteratsiya 1: DEQUEUE 2, 2
  2 = 2 ✓
  ENQUEUE 2.left=3, 2.right=3   (tashqi juft)
  ENQUEUE 2.right=4, 2.left=4  (ichki juft)
  queue: [3, 3, 4, 4]

Iteratsiya 2: DEQUEUE 3, 3
  3 = 3 ✓
  ENQUEUE NULL, NULL
  ENQUEUE NULL, NULL
  queue: [4, 4, NULL, NULL, NULL, NULL]

Iteratsiya 3: DEQUEUE 4, 4
  4 = 4 ✓
  ENQUEUE NULL, NULL
  ENQUEUE NULL, NULL
  queue: [NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL]

Iteratsiya 4-7: DEQUEUE NULL, NULL → CONTINUE

Navbat bo'sh → RETURN TRUE

Vaqt va xotira murakkabligi

Yondashuv	Vaqt	Xotira	Eslatma
Rekursiv	`O(n)`	`O(h)`	Call stack
Iterativ BFS	`O(n)`	`O(w)`	Navbat hajmi

Barcha n tugun bir marta ko'riladi — O(n). Rekursiv call stack balandlikka O(h) xotira. Muvozanatlangan daraxtda O(log n), zanjirda O(n).

Edge case'lar

Bo'sh daraxt. root = NULL → TRUE. Aniqlik bo'yicha, bo'sh daraxt simmetrik.

Bitta tugunli daraxt. Ildiz bor, bolalari yo'q. IS_MIRROR(NULL, NULL) = TRUE → simmetrik.

Faqat chap yoki o'ng bola. IS_MIRROR(node, NULL) → FALSE. To'g'ri: asimmetrik.

Qiymatlari teng, tuzilishi boshqacha. [1, 2, 2, NULL, 3, NULL, 3] — qiymatlar simmetrik ko'rinadi, lekin tuzilma emas. Rekursiya tuzilmani ham tekshiradi — to'g'ri.

Barcha qiymatlari teng. [1, 1, 1, 1, 1, 1, 1] — simmetrik bo'lishi uchun tuzilmasi ham simmetrik bo'lishi kerak. Agar daraxt to'liq binar daraxt bo'lsa — simmetrik.

Note

IS_MIRROR funksiyasi chap va o'ng daraxtlarni alohida argument sifatida oladi, nafaqat bitta daraxtni. Bu IS_SYMMETRICdan farqli: IS_SYMMETRIC ildizdan boshlab, IS_MIRROR esa ikkita "ko'zgudagi" tugunni solishtiradi.

Simmetriya va boshqa daraxt masalalariga aloqasi

Daraxtni akslantirish (invert) bilan solishtirish: akslantirish daraxtni o'zgartiradi, simmetrik tekshirish esa o'zgartirmaydi — faqat o'qiydi.

Daraxt nusxasi (same tree): ikkita daraxtni solishtirish — IS_MIRROR bilan o'xshash mantiq, lekin left.left va right.left solishtiriladi (ko'zgusiz).

IS_SAME(left, right):
  ...
  RETURN IS_SAME(left.left,  right.left) AND   // ko'zgusiz
         IS_SAME(left.right, right.right)

IS_MIRROR(left, right):
  ...
  RETURN IS_MIRROR(left.left,  right.right) AND  // ko'zguda
         IS_MIRROR(left.right, right.left)

Xulosa

Simmetrik daraxt masalasi ko'zgudagi simmetriyani rekursiv solishtirish orqali yechiladi. IS_MIRROR(left, right) funksiyasi ikkita "ko'zgudagi" tugunni solishtirib, left.left ni right.right bilan va left.right ni right.left bilan tekshiradi.

Uchta base case muhim: ikkisi ham NULL → simmetrik; bittasi NULL → asimmetrik; qiymatlari teng emas → asimmetrik.

Iterativ versiya xuddi shu mantiqni navbat yordamida amalga oshiradi — juft-juft solishtirish tartibini aniq ko'rsatadi.