Temu Duga Pengekodan: Mencari Lowest Common Ancestor bagi Binary Tree

Masalah dan Skop

Diberikan satu binary tree sebarangan dan dua nod berbeza p dan q di dalamnya, kembalikan lowest common ancestor (leluhur sepunya terendah) bagi kedua-duanya. Sesuatu nod ialah leluhur kepada dirinya sendiri. LCA ialah nod paling dalam yang subpokoknya mengandungi kedua-dua sasaran, jadi jika p ialah leluhur kepada q, jawapannya ialah p itu sendiri.

Empat butiran mentakrifkan kontrak asas: pokok ini bukan binary search tree; input mengenal pasti objek nod dan bukannya nilai; nod berasingan boleh mempunyai nilai yang sama; dan kedua-dua p serta q dijamin berada di dalam pokok. Membandingkan nilai secara senyap melanggar kontrak tersebut. Menggunakan semula rekursi asas selepas membuang jaminan kewujudan juga menghasilkan positif palsu yang sukar dikesan.

a
      /   \
     b     c
    / \   / \
   d   e f   g
        \
         h

Di sini, LCA(d, h) = b, LCA(b, h) = b, dan LCA(e, f) = a. Soalan ini menyasarkan jurutera perisian yang dijangka memahami penjelajahan pokok (tree traversal), semantik rekursif, dan kerumitan. Kes asas memerlukan satu pertanyaan. Kedalaman tanpa batas, ketiadaan sasaran, penunjuk induk (parent pointer), atau banyak pertanyaan terhadap satu pokok statik ialah kekangan susulan yang mengubah penyelesaian terbaik.

Perkara yang Dinilai oleh Penemu Duga

Pemerhatian berguna yang pertama menukarkan konsep "terendah" kepada struktur: jawapannya ialah nod sepunya terakhir pada laluan punca-ke-p dan punca-ke-q. Menyimpan kedua-dua laluan adalah betul, tetapi tidak perlu. Penerbitan yang lebih tepat meminta setiap subpokok melaporkan salah satu daripada tiga keadaan: tiada sasaran ditemui, satu sasaran ditemui, atau titik di mana kedua-dua sasaran telah pun bertemu.

Jawapan yang kukuh mentakrifkan nilai pulangan rekursif secara tepat. Bagi subpokok yang berakar pada node, fungsi tersebut mengembalikan:

• null apabila subpokok tidak mengandungi p mahupun q;
• p atau q apabila satu sasaran yang ditemui mesti disebarkan ke atas;
• nod lain apabila nod tersebut telah pun menjadi LCA di dalam subpokok ini.

Apabila kedua-dua hasil rekursif bukan sifar (non-null), sasaran-sasaran tersebut bertemu melalui sisi berbeza pada nod semasa, maka nod semasa ialah jawapannya. Apabila hanya satu sisi bukan sifar, hasilnya disebarkan. Kes asas kembali serta-merta apabila nod semasa ialah sasaran kerana kewujudannya dijamin: jika sasaran satu lagi berada di bawahnya, nod ini ialah LCA; jika tidak, nod ini mesti melaporkan satu sasaran kepada leluhur.

Perangkap kontrak ini sangat penting. Jika q tidak wujud, algoritma asas boleh mengembalikan p; ia tidak membuktikan bahawa kedua-dua sasaran benar-benar wujud. Sebaik sahaja jaminan itu dikeluarkan, hasil rekursif memerlukan kiraan padanan (match count). Bagi pokok dengan n nod dan ketinggian h, satu pertanyaan melawat setiap nod dalam kes terburuk, jadi masa yang diambil ialah O(n) dan timbunan (stack) rekursif ialah O(h). Dalam pokok yang condong (skewed tree), h = n, dan timbunan panggilan boleh menjadi punca kegagalan dan bukannya beban kerja algoritma.

Soalan untuk Dijelaskan Terlebih Dahulu

• Adakah input merupakan rujukan nod atau nilai? Rujukan membenarkan nilai pendua, jadi bandingkan dengan node === p. Carian nilai hanya sah apabila keunikan nilai adalah sebahagian daripada kontrak.
• Adakah kedua-dua sasaran dijamin wujud dan berbeza? Rekursi asas bergantung pada kewujudan. Jika salah satu boleh tiada, kembalikan juga kiraan padanan. Jika p === q dibenarkan, tentukan sama ada mencari objek itu sekali sudah memadai.
• Adakah ini binary tree sebarangan atau binary search tree? Pokok sebarangan memerlukan carian struktur. BST boleh mengikut susunan kunci pada satu laluan, tetapi kunci pendua dan identiti rujukan boleh membatalkan jalan pintas tersebut.
• Apakah bilangan nod dan ketinggian maksimum? Pokok yang seimbang mempunyai kedalaman rekursi O(log n). Rantaian 100,000 nod memerlukan timbunan eksplisit dan pemetaan induk (parent map) untuk mengelakkan limpahan timbunan (stack overflow) pada masa larian.
• Berapa banyak pertanyaan yang menyasarkan pokok statik yang sama? Pertanyaan tunggal lebih sesuai menggunakan DFS secara terus. Banyak pertanyaan boleh mewajarkan pra-pengiraan kedalaman dan 2^k leluhur untuk pertanyaan O(log n).
• Adakah nod sudah mempunyai penunjuk induk? Jika ya, punca tidak perlu dijelajahi. Selaraskan kedalaman dan bergerak ke atas bersama-sama, atau rekodkan satu rantaian leluhur dan cari persilangan pertamanya.

Rangka Kerja Jawapan 30 Saat

"Mula-mula saya akan mengesahkan bahawa ini ialah binary tree sebarangan dan p serta q ialah rujukan nod yang dijamin wujud, jadi nilai pendua tidak menjejaskan identiti. Fungsi rekursif saya mengembalikan sasaran atau LCA yang ditemui dalam subpokok. Nod sifar mengembalikan null, dan nod yang sama dengan p atau q mengembalikan dirinya sendiri. Selepas mencari kedua-dua anak, dua hasil bukan sifar bermakna sasaran bertemu pada nod semasa; jika tidak, saya menyebarkan satu hasil bukan sifar tersebut. Setiap nod dilawati paling banyak sekali, menghasilkan masa kes terburuk O(n) dan ruang timbunan O(h). Saya akan menguji cabang berasingan, sasaran yang merupakan leluhur, nilai pendua, dan pokok condong. Jika sasaran mungkin tiada, saya menambah kiraan padanan; jika ketinggian tidak terbatas, saya menggunakan timbunan eksplisit untuk membina pautan induk."

Penyelesaian Langkah demi Langkah

Langkah 1: Wujudkan Garis Dasar Laluan yang Betul

Pendekatan paling terus mencari laluan punca-ke-p dan punca-ke-q, membandingkannya dari punca, dan mengembalikan nod sepunya terakhirnya. Ia menerangkan definisi dengan jelas dan secara semula jadi mengesahkan bahawa kedua-dua sasaran wujud. Dua laluan DFS masih mengambil masa O(n), manakala laluan dan rekursi menggunakan ruang O(h). Pelaksanaan yang mengekalkan setiap nod yang diterokai boleh berkembang kepada ruang O(n).

Kelebihan yang berulang (redundancy) ialah kedua-dua carian melintasi awalan sepunya (shared prefix) yang besar. Satu-satunya maklumat yang diperlukan ialah apa yang dilaporkan oleh subpokok kepada induknya, jadi kedua-dua laluan boleh dimampatkan ke dalam satu penjelajahan postorder.

Langkah 2: Takrifkan Nilai Pulangan dan Jelajah Sekali Sahaja

interface TreeNode {
  value: number
  left: TreeNode | null
  right: TreeNode | null
}

function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode,
): TreeNode | null {
  if (root === null || root === p || root === q) {
    return root
  }

  const left = lowestCommonAncestor(root.left, p, q)
  const right = lowestCommonAncestor(root.right, p, q)

  if (left !== null && right !== null) {
    return root
  }

  return left ?? right
}

Kod ini membandingkan identiti objek dan tidak pernah membaca value, jadi nilai yang sama pada nod berasingan adalah selamat. Postorder adalah penting: nod semasa memerlukan kedua-dua laporan anak sebelum memutuskan sama ada ia merupakan titik pertemuan pertama.

Langkah 3: Buktikannya dengan Varian Tak Berubah (Invariant)

Pertimbangkan mana-mana subpokok yang berakar pada node, dan anggap kedua-dua panggilan rekursif memenuhi takrifan nilai pulangan.

1. Jika node adalah sifar, subpokok tidak mengandungi sasaran, jadi null adalah betul.
2. Jika node ialah p atau q, kembalikan node. Oleh kerana kedua-dua sasaran wujud, sasaran ini sama ada LCA kerana ia mengandungi sasaran yang satu lagi, atau ia mesti melaporkan satu sasaran kepada leluhur.
3. Jika kedua-dua hasil anak adalah bukan sifar, setiap sisi melaporkan sasaran. Tiada nod yang lebih dalam kepunyaan kedua-dua belah pihak, jadi node ialah leluhur sepunya paling dalam.
4. Jika tepat satu sisi bukan sifar, nod semasa tidak mewujudkan titik pertemuan baharu. Sasaran atau LCA yang telah lengkap di sisi tersebut adalah satu-satunya hasil yang sah untuk disebarkan. Jika kedua-duanya sifar, kembalikan null.

Melalui aruhan struktur, hasil yang dikembalikan pada punca ialah LCA bagi keseluruhan pokok. Bukti ini juga meliputi kes leluhur yang mudah terlepas pandang: apabila p ialah leluhur kepada q, mencapai p akan mengembalikannya tanpa memerlukan q dikembalikan dari bawah untuk kali kedua.

Langkah 4: Nyatakan Kos Masa dan Ruang Sebenar

Dalam kes terburuk, fungsi melawati kesemua n nod dan melaksanakan operasi malar pada setiap satu, jadi masa ialah O(n). Menemui sasaran lebih awal boleh melangkau sebahagian daripada pokok, tetapi kes terbaik bukanlah batas kes terburuk.

Ruang tambahan (auxiliary space) ialah O(h) untuk rekursi. Dalam pokok yang seimbang, h = O(log n); dalam pokok yang condong sepenuhnya, h = n. Rujukan nod yang dikembalikan tidak dikira sebagai simpanan tambahan. Menyatakan bahawa penyelesaian ini menggunakan ruang O(1) bermakna mengabaikan timbunan panggilan.

Langkah 5: Ubah Kontrak Apabila Sasaran Mungkin Tiada

Tanpa jaminan kewujudan, fungsi asas boleh memberikan jawapan palsu: jika hanya p wujud dalam pokok, ia menyebarkan p sehingga ke punca. Versi yang selamat membezakan antara nod calon dengan bilangan sasaran yang sebenarnya ditemui.

interface SearchResult {
  candidate: TreeNode | null
  matches: number
}

function lowestCommonAncestorValidated(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode,
): TreeNode | null {
  function visit(node: TreeNode | null): SearchResult {
    if (node === null) {
      return { candidate: null, matches: 0 }
    }

    const left = visit(node.left)
    if (left.matches === 2) {
      return left
    }

    const right = visit(node.right)
    if (right.matches === 2) {
      return right
    }

    const self = node === p || node === q ? 1 : 0
    const matches = left.matches + right.matches + self

    return {
      candidate: matches === 2 ? node : left.candidate ?? right.candidate ?? (self ? node : null),
      matches,
    }
  }

  const result = visit(root)
  return result.matches === 2 ? result.candidate : null
}

Versi ini masih mengandaikan p !== q. Jika rujukan yang sama mungkin dibekalkan dua kali, tentukan kontrak terlebih dahulu: mencari nod tersebut sekali sepatutnya mengembalikannya dan bukannya terus memerlukan matches === 2. Perubahan kekangan harus mendahului perubahan kod.

Langkah 6: Gunakan Timbunan Eksplisit dan Pemetaan Induk untuk Pokok yang Sangat Dalam

Apabila ketinggian boleh menghampiri 100,000, ruang rekursi asimptotik tidak berubah, tetapi timbunan panggilan masa larian mungkin melimpah (overflow) terlebih dahulu. Jelajah dengan timbunan eksplisit dan rekod parent.get(child) = node sehingga kedua-dua p dan q berada dalam peta. Masukkan setiap leluhur p ke dalam satu set, kemudian berjalan ke atas dari q; ahli set yang pertama ditemui ialah LCA.

Alternatif ini masih mengambil masa O(n) dan menggunakan ruang eksplisit O(n). Ia mungkin menggunakan lebih banyak ingatan heap berbanding rekursi, tetapi memindahkan beban sumber daripada timbunan panggilan yang kecil kepada struktur data yang terkawal. Untuk satu pertanyaan pada pokok dengan batas ketinggian yang munasabah, versi rekursif adalah lebih pendek dan lebih mudah dibuktikan, jadi pemetaan induk tidak sepatutnya menjadi pilihan lalai automatik.

Langkah 7: Sahkan Semantik dengan Kes Adversarial

Sekurang-kurangnya, rangkumi matriks ini:

Selain contoh tetap, jana pokok-pokok kecil secara rawak dan bandingkan hasil satu laluan dengan garis dasar laluan mengikut identiti objek. Oleh kerana kaedah garis dasar dan kaedah yang dioptimumkan menggunakan pendekatan yang berbeza, semakan perbezaan ini menangkap lebih banyak kecacatan berbanding beberapa penegasan (assertions) yang dipilih secara manual sahaja.

Contoh Jawapan Berkualiti Tinggi

"Mula-mula saya akan menetapkan kontrak: ini ialah binary tree sebarangan, p dan q ialah rujukan nod berbeza yang dijamin wujud, dan nilai mungkin berulang. Oleh itu, kod saya membandingkan rujukan, bukan nilai.

Saya menggunakan satu DFS postorder. Bagi sesuatu subpokok, fungsi mengembalikan null, satu sasaran yang ditemui, atau LCA yang telah ditemui. Nod sifar mengembalikan null, dan nod semasa yang sama dengan mana-mana sasaran mengembalikan dirinya sendiri. Selepas membuat rekursi ke dalam kedua-dua anak, dua hasil bukan sifar bermakna sasaran bertemu buat kali pertama pada nod semasa, jadi saya mengembalikannya. Dengan hanya satu sisi bukan sifar, saya menyebarkan hasil tersebut.

Ketepatan algoritma ini bersandarkan varian tak berubah nilai pulangan tersebut. Apabila sasaran berada dalam subpokok anak yang berbeza, tiada nod yang lebih dalam boleh mengandungi kedua-duanya. Apabila satu sasaran ialah leluhur kepada sasaran yang satu lagi, mengembalikan sasaran leluhur tersebut serta-merta menepati definisi. Kes terburuk melawati setiap nod sekali untuk masa O(n), dengan ruang timbunan rekursif O(h); pokok yang condong menjadikan kedalaman timbunan O(n).

Saya akan menguji cabang bertentangan, sasaran leluhur, satu subpokok yang dalam, dan nilai pendua. Jika sasaran tidak dijamin wujud, fungsi ini boleh mengembalikan satu sasaran yang wujud itu, jadi saya juga akan mengembalikan kiraan padanan dan hanya menerima calon selepas menemui kedua-duanya. Jika pokok boleh menjadi sangat dalam, saya akan menggunakan timbunan eksplisit dan pemetaan induk untuk mengelakkan limpahan timbunan panggilan."

Kesilapan Biasa

• Menganggap pokok sebagai BST dan memilih sisi mengikut nilai → binary tree sebarangan tiada susunan kunci, dan nilai pendua tidak mengenal pasti nod → cari struktur dan bandingkan rujukan nod.
• Mengembalikan nod semasa apabila salah satu anak bukan sifar → sasaran tunggal pada satu sisi dipromosikan sehingga ke punca → kembalikan nod semasa hanya apabila kedua-dua sisi bukan sifar; jika tidak, sebarkan hasil bukan sifar tersebut.
• Mengandaikan p mesti berada betul-betul di bawah jawapan → sesuatu nod ialah leluhur kepada dirinya sendiri, jadi p boleh menjadi jawapannya → jadikan identiti nod semasa sebagai kes asas.
• Menggunakan semula algoritma asas apabila sasaran boleh tiada → mencari satu sasaran masih menghasilkan nilai bukan sifar → kembalikan kiraan padanan dan berjaya hanya selepas menemui kedua-duanya.
• Mendakwa ruang tambahan O(1) → bingkai rekursif bertambah mengikut ketinggian pokok dan mencapai O(n) pada rantaian → laporkan O(h) dan gunakan timbunan eksplisit apabila kedalaman tidak terbatas.
• Membuat pra-pengiraan binary lifting untuk satu pertanyaan sahaja → kod dan simpanan O(n log n) tidak dilunaskan (amortized) → gunakan satu DFS untuk satu pertanyaan dan lakukan pra-pemprosesan hanya untuk banyak pertanyaan.
• Hanya menguji dua daun pada sisi bertentangan → pepijat berkaitan leluhur, nilai pendua, sasaran hilang, dan kedalaman kekal tersembunyi → susun ujian berdasarkan sempadan kontrak.

Soalan Susulan

Bagaimana jika p atau q mungkin tiada dalam pokok?

Kembalikan nod calon dan kiraan padanan daripada rekursi. Dengan sasaran yang berbeza, kiraannya ialah 0, 1, atau 2. Kembalikan calon LCA hanya apabila hasil punca mempunyai kiraan 2; jika tidak kembalikan null. Menjalankan algoritma asas dan sekadar menyemak hasil bukan sifar adalah tidak mencukupi kerana satu sasaran yang wujud itu sendiri adalah bukan sifar.

Bagaimana jika pokok mempunyai 100,000 nod dan mungkin condong sepenuhnya?

Gunakan timbunan eksplisit untuk membina pemetaan induk. Selepas kedua-dua sasaran ditemui, simpan leluhur p dalam satu set dan ikuti rantaian induk q sehingga persilangan pertama. Ia mengambil masa O(n) dan ruang heap O(n) tetapi tidak menggunakan 100,000 bingkai panggilan bahasa pengaturcaraan. Jika ruang heap juga terhad, jelaskan sama ada penunjuk induk atau antara muka penjelajahan terkawal tersedia dan bukannya mengandaikan rekursi adalah selamat.

Bagaimana jika pokok statik yang sama mesti menjawab satu juta pertanyaan LCA?

DFS dengan O(n) bagi setiap pertanyaan tidak lagi sesuai. Lakukan pra-pengiraan kedalaman setiap nod dan 2^k leluhurnya dalam masa dan ruang O(n log n). Bagi setiap pertanyaan, angkat nod yang lebih dalam ke kedalaman yang sama, kemudian angkat kedua-duanya dari k terbesar ke bawah, menghasilkan masa O(log n) bagi setiap pertanyaan. Pada volum pertanyaan yang lebih besar, Euler tour bersama RMQ mungkin wajar dinilai; kekerapan kemas kini, keperluan memori dan kependaman (latency) menentukan skema pra-pemprosesan yang sesuai.

Bagaimana jika setiap nod sudah mempunyai penunjuk induk?

Tiada keperluan untuk menjelajah dari punca. Kira kedua-dua kedalaman, naikkan nod yang lebih dalam sehingga kedalamannya sama, kemudian gerakkan kedua-duanya ke atas sehingga kedua-duanya sama. Ini mengambil masa O(h) dan ruang tambahan O(1). Sebagai alternatif, simpan semua leluhur p dan berjalan ke atas dari q; pendekatan ini lebih mudah tetapi menggunakan set sebesar O(h).

Bagaimanakah penyelesaian berubah untuk binary search tree?

Dengan kunci unik dan kontrak yang mencari sasaran mengikut kunci, pergi ke kiri apabila kedua-dua kunci sasaran lebih kecil, ke kanan apabila kedua-duanya lebih besar, dan jika tidak, kembalikan titik pemisahan semasa atau sasaran. Ini mengambil masa O(h) dan ruang lelaran O(1). Jika nilai boleh berulang atau input masih mengenal pasti sasaran mengikut rujukan, tentukan penempatan kunci pendua dan semantik carian terlebih dahulu; dua nilai sahaja tidak boleh menggantikan algoritma pokok sebarangan dengan selamat.