Ketinggian Pokok Binari Selepas Pertanyaan Penyingkiran Subtree

2458. Ketinggian Pokok Binari Selepas Pertanyaan Penyingkiran Subtree

Kesukaran: Sukar

Topik: Tatasusunan, Pokok, Carian Pertama Kedalaman, Carian Luas-Pertama, Pokok Binari

Anda diberi akar pokok binari dengan n nod. Setiap nod diberikan nilai unik dari 1 hingga n. Anda juga diberikan pertanyaan tatasusunan bersaiz m.

Anda perlu melakukan pertanyaan bebas pada pokok di mana dalam pertanyaan i^th anda melakukan perkara berikut:

• Alih keluar subpokok yang berakar pada nod dengan pertanyaan nilai[i] daripada pokok. dijamin pertanyaan[i] akan tidak sama dengan nilai punca.

Kembalikan jawapan tatasusunan bersaiz m dengan jawapan[i] ialah ketinggian pokok selepas melakukan pertanyaan i^ke.

Nota:

• Pertanyaan adalah bebas, jadi pokok itu kembali kepada keadaan awal selepas setiap pertanyaan.
• Ketinggian pokok ialah bilangan tepi dalam laluan mudah terpanjang dari akar ke beberapa nod dalam pokok.

Contoh 1:

• Input: akar = [1,3,4,2,null,6,5,null,null,null,null,null,7], pertanyaan = [4]
• Output: [2]
• Penjelasan: Gambar rajah di atas menunjukkan pokok selepas mengalih keluar subpokok yang berakar pada nod dengan nilai 4.
  • Ketinggian pokok ialah 2 (Laluan 1 -> 3 -> 2).

Contoh 2:

• Input: akar = [5,8,9,2,1,3,7,4,6], pertanyaan = [3,2,4,8]
• Output: [3,2,3,2]
• Penjelasan: Kami mempunyai pertanyaan berikut:
  • Mengalih keluar subpokok yang berakar pada nod dengan nilai 3. Ketinggian pokok menjadi 3 (Laluan 5 -> 8 -> 2 -> 4).
  • Mengalih keluar subpokok yang berakar pada nod dengan nilai 2. Ketinggian pokok menjadi 2 (Laluan 5 -> 8 -> 1).
  • Mengalih keluar subpokok yang berakar pada nod dengan nilai 4. Ketinggian pokok menjadi 3 (Laluan 5 -> 8 -> 2 -> 6).
  • Mengalih keluar subpokok yang berakar pada nod dengan nilai 8. Ketinggian pokok menjadi 2 (Laluan 5 -> 9 -> 3).

Kekangan:

• Bilangan nod dalam pokok ialah n.
• 2 <= n <= 10⁵
• 1 <= Node.val <= n
• Semua nilai dalam pokok adalah unik.
• m == pertanyaan.panjang
• 1 <= m <= min(n, 10⁴)
• 1 <= pertanyaan[i] <= n
• pertanyaan[i] != root.val

Petunjuk:

1. Cuba prakirakan jawapan bagi setiap nod daripada 1 hingga n, dan jawab setiap pertanyaan dalam O(1).
2. Jawapan boleh diprakira dalam satu lintasan pokok selepas mengira ketinggian setiap subpokok.

Penyelesaian:

Penyelesaian menggunakan pendekatan dua hala:

1. Kira ketinggian setiap nod dalam pokok.
2. Tentukan ketinggian maksimum pokok selepas mengalih keluar subpokok yang berakar pada setiap nod yang ditanya.

Mari laksanakan penyelesaian ini dalam PHP: 2458. Ketinggian Pokok Binari Selepas Pertanyaan Penyingkiran Subtree

Pecahan Kod

1. Definisi dan Sifat Kelas:

class Solution {

    private $valToMaxHeight = [];
    private $valToHeight = [];

• valToMaxHeight: Tatasusunan ini akan menyimpan ketinggian maksimum pokok selepas mengalih keluar setiap subpokok nod.
• valToHeight: Tatasusunan ini akan menyimpan ketinggian setiap subpokok nod.

2. Fungsi Utama:

function treeQueries($root, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

• Fungsi treeQueries mengambil akar pokok dan tatasusunan pertanyaan.
• Ia mula-mula memanggil fungsi ketinggian untuk mengira ketinggian setiap nod.
• Kemudian, ia memanggil fungsi dfs (carian pertama mendalam) untuk mengira ketinggian maksimum selepas penyingkiran subpokok.
• Akhir sekali, ia mengisi tatasusunan jawapan dengan keputusan untuk setiap pertanyaan.

3. Pengiraan Ketinggian:

private function height($node) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

• Fungsi ini mengira ketinggian setiap nod secara rekursif.
• Jika nod adalah nol, ia mengembalikan 0.
• Jika ketinggian nod sudah dikira, ia mendapatkannya semula daripada cache (valToHeight).
• Ia mengira ketinggian berdasarkan ketinggian anak kiri dan kanannya dan menyimpannya dalam valToHeight.

4. Carian Pertama Kedalaman untuk Ketinggian Maksimum:

private function dfs($node, $depth, $maxHeight) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

• Fungsi ini melaksanakan DFS untuk mengira ketinggian maksimum pokok selepas setiap subpokok nod dialih keluar.
• Ia merekodkan ketinggian maksimum semasa dalam valToMaxHeight untuk nod semasa.
• Ia mengira ketinggian subpokok kiri dan kanan serta mengemas kini ketinggian maksimum dengan sewajarnya.
• Ia secara rekursif memanggil dirinya untuk anak kiri dan kanan, mengemas kini kedalaman dan ketinggian maksimum.

Contoh Panduan

Mari kita lihat contoh langkah demi langkah.

Contoh Input:

// Tree Structure
//        1
//       / \
//      3   4
//     /   / \
//    2   6   5
//         \
//          7

$root = [1, 3, 4, 2, null, 6, 5, null, null, null, null, null, 7];
$queries = [4];

Pengiraan Ketinggian Awal:

• Ketinggian pokok berakar pada 1: 3
• Ketinggian pokok berakar pada 3: 2
• Ketinggian pokok berakar pada 4: 2 (ketinggian subpokok berakar pada 6 dan 5)
• Ketinggian pokok berakar pada 6: 1 (hanya nod 7)
• Ketinggian pokok berakar pada 2: 0 (simpul daun)

Selepas pengiraan ketinggian, valToHeight akan kelihatan seperti ini:

class Solution {

    private $valToMaxHeight = [];
    private $valToHeight = [];

DFS untuk Max Heights:

• Untuk akar (1), keluarkan subpokok 4 daun:
  • Tinggi Kiri: 2 (berakar pada 3)
  • Tinggi Kanan: 1 (berakar pada 5)
• Oleh itu, ketinggian maksimum selepas mengeluarkan 4 ialah 2.

Susun Keputusan Selepas Pertanyaan:

• Untuk pertanyaan 4, hasilnya ialah [2].

Output Akhir

Hasil untuk input yang diberikan ialah:

function treeQueries($root, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

Pendekatan berstruktur ini memastikan kami mengira ketinggian yang diperlukan dengan cekap dan menjawab setiap pertanyaan dalam masa yang tetap selepas prapemprosesan awal. Kerumitan keseluruhan ialah O(n m), dengan n ialah bilangan nod dalam pokok dan m ialah bilangan pertanyaan.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

• LinkedIn
• GitHub

Atas ialah kandungan terperinci Ketinggian Pokok Binari Selepas Pertanyaan Penyingkiran Subtree. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!