. Cari Nilai Terbesar dalam Setiap Baris Pokok

515. Cari Nilai Terbesar dalam Setiap Baris Pokok

Kesukaran: Sederhana

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

Memandangkan akar pokok binari, kembalikan tatasusunan nilai terbesar dalam setiap baris pokok (0-diindeks).

Contoh 1:

• Input: punca = [1,3,2,5,3,null,9]
• Output: [1,3,9]

Contoh 2:

• Input: akar = [1,2,3]
• Output: [1,3]

Kekangan:

• Bilangan nod dalam pepohon akan berada dalam julat [0, 10⁴].
• -2³¹ <= Node.val <= 2³¹ - 1

Penyelesaian:

Masalahnya "Cari Nilai Terbesar dalam Setiap Baris Pokok" memerlukan mengenal pasti nilai terbesar yang terdapat pada setiap peringkat (baris) pokok binari. Memandangkan pokok binari, matlamatnya adalah untuk melintasi baris pokok demi baris dan mengumpul nilai maksimum daripada setiap baris. Masalah ini melibatkan teknik rentas pokok asas seperti Breadth-First Search (BFS) atau Depth-First Search (DFS).

Perkara Penting

1. Tree Traversal: Penyelesaian melibatkan merentasi semua peringkat pokok binari untuk mengenal pasti nilai terbesar pada setiap peringkat.
2. Breadth-First Search (BFS): BFS sesuai untuk traversal peringkat demi peringkat, yang memudahkan pencarian nilai terbesar dalam setiap baris.
3. Kekangan: Kendalikan kes tepi seperti pokok kosong dan nod dengan nilai integer besar atau kecil dalam julat kekangan.

Pendekatan

Pendekatan paling mudah untuk mencari nilai terbesar dalam setiap baris ialah menggunakan BFS:

• Melintasi aras pokok mengikut aras.
• Untuk setiap peringkat, jejaki nilai terbesar.

Sebagai alternatif, DFS juga boleh digunakan:

• Melintasi pokok secara rekursif dan mengekalkan rekod nilai maksimum pada setiap kedalaman.

Rancang

1. Mulakan tatasusunan untuk menyimpan nilai terbesar bagi setiap baris.
2. Gunakan baris gilir untuk traversal BFS:
   • Mulakan dengan nod akar.
   • Proses semua nod pada tahap semasa sebelum beralih ke tahap seterusnya.
3. Untuk setiap peringkat:
   • Lelaran melalui semua nod dan cari nilai maksimum.
   • Tambahkan nilai ini pada tatasusunan hasil.
4. Kembalikan tatasusunan hasil selepas melengkapkan traversal.

Langkah Penyelesaian

1. Semak Input: Jika akarnya nol, kembalikan tatasusunan kosong.
2. Sediakan BFS:
   • Gunakan baris gilir yang dimulakan dengan nod akar.
   • Mulakan tatasusunan hasil kosong.
3. Tahap Traverse:
   • Untuk setiap tahap, jejak nilai maksimum.
   • Tambahkan nod anak pada baris gilir untuk tahap seterusnya.
4. Kemas Kini Keputusan:
   • Tambahkan nilai maksimum setiap tahap pada tatasusunan hasil.
5. Kembalikan Keputusan: Kembalikan tatasusunan hasil yang mengandungi nilai terbesar untuk setiap baris.

Mari laksanakan penyelesaian ini dalam PHP: 515. Cari Nilai Terbesar dalam Setiap Baris Pokok

val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

/**
 * @param TreeNode $root
 * @return Integer[]
 */
function largestValues($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$root = new TreeNode(1);
$root->left = new TreeNode(3);
$root->right = new TreeNode(2);
$root->left->left = new TreeNode(5);
$root->left->right = new TreeNode(3);
$root->right->right = new TreeNode(9);

print_r(largestValues($root)); // Output: [1, 3, 9]
?>





  
  
  Penjelasan:



  
  
  Input: [1,3,2,5,3,null,9]




Tahap 0: Nilai nod: [1] → Maksimum: 1.

Tahap 1: Nilai nod: [3, 2] → Maksimum: 3.

Tahap 2: Nilai nod: [5, 3, 9] → Maksimum: 9.
#### Output: [1, 3, 9].



  
  
  Kerumitan Masa




BFS Traversal: Setiap nod diproses sekali → O(n).

Mencari Maksimum: Dilakukan semasa traversal → O(1) setiap tahap.

Jumlah: O(n).



  
  
  Kerumitan Angkasa




Storan Beratur: Paling banyak, lebar pokok (bilangan nod pada tahap terbesar) → O(w) dengan w ialah lebar maksimum pokok.



  
  
  Output sebagai Contoh


Input: akar = [1,3,2,5,3,null,9]


Output: [1, 3, 9].

Penyelesaian berasaskan BFS ini secara cekap mengira nilai terbesar dalam setiap baris pokok dengan kerumitan masa linear. Ia mengendalikan pokok besar, nilai negatif dan bekas tepi seperti pokok kosong dengan berkesan.

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 . Cari Nilai Terbesar dalam Setiap Baris Pokok. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!