Kth Jumlah Terbesar dalam Pokok Perduaan

2583. Kth Jumlah Terbesar dalam Pokok Binari

Kesukaran: Sederhana

Topik: Pokok, Keluasan Carian Pertama, Isih, Pokok Binari

Anda diberi punca pokok binari dan integer positif k.

Jumlah peringkat dalam pepohon ialah jumlah nilai nod yang berada pada tahap sama.

Kembalikan jumlah tahap ke^ke terbesar dalam pokok (tidak semestinya berbeza). Jika terdapat kurang daripada k aras dalam pokok, kembalikan -1.

Perhatikan bahawa dua nod berada pada tahap yang sama jika mereka mempunyai jarak yang sama dari punca.

Contoh 1:

• Input: punca = [5,8,9,2,1,3,7,4,6], k = 2
• Output: 13
• Penjelasan: Jumlah tahap adalah seperti berikut:
  • Tahap 1: 5.
  • Tahap 2: 8 9 = 17.
  • Tahap 3: 2 1 3 7 = 13.
  • Tahap 4: 4 6 = 10.
  • Jumlah peringkat ke-2^nd terbesar ialah 13.

Contoh 2:

• Input: punca = [1,2,null,3], k = 1
• Output: 3
• Penjelasan: Jumlah tahap terbesar ialah 3.

Kekangan:

• Bilangan nod dalam pokok ialah n.
• 2 <= n <= 10⁵
• 1 <= Node.val <= 10⁶
• 1 <= k <= n

Petunjuk:

1. Cari jumlah nilai nod pada setiap tahap dan kembalikan nilai ke-k terbesar.
2. Untuk mencari jumlah nilai nod pada setiap tahap, anda boleh menggunakan algoritma DFS atau BFS untuk melintasi pepohon dan menjejaki tahap setiap nod.

Penyelesaian:

Kami akan mengikuti langkah ini:

1. Level Order Traversal: Kami akan menggunakan Breadth-First Search (BFS) untuk merentasi peringkat pokok mengikut tahap.
2. Kira Jumlah Tahap: Semasa traversal BFS, kami akan mengira jumlah nilai nod pada setiap tahap.
3. Isih dan Cari Jumlah Terbesar ke-k: Selepas mengira jumlah untuk semua peringkat, kami akan mengisih jumlah dan mendapatkan nilai ke-k terbesar.

Mari kita laksanakan penyelesaian ini dalam PHP: 2583. Kth Jumlah Terbesar dalam Pokok Perduaan

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

/**
 * @param TreeNode $root
 * @param Integer $k
 * @return Integer
 */
function kthLargestLevelSum($root, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1:
// Input: root = [5,8,9,2,1,3,7,4,6], k = 2
$root1 = new TreeNode(5);
$root1->left = new TreeNode(8);
$root1->right = new TreeNode(9);
$root1->left->left = new TreeNode(2);
$root1->left->right = new TreeNode(1);
$root1->right->left = new TreeNode(3);
$root1->right->right = new TreeNode(7);
$root1->left->left->left = new TreeNode(4);
$root1->left->left->right = new TreeNode(6);
echo kthLargestLevelSum($root1, 2); // Output: 13

// Example 2:
// Input: root = [1,2,null,3], k = 1
$root2 = new TreeNode(1);
$root2->left = new TreeNode(2);
$root2->left->left = new TreeNode(3);
echo kthLargestLevelSum($root2, 1); // Output: 3
?>





  
  
  Penjelasan:



Kelas TreeNode: Kami mentakrifkan kelas TreeNode untuk mewakili nod dalam pokok binari, di mana setiap nod mempunyai nilai (val), anak kiri (kiri) dan anak kanan (kanan).
BFS Traversal: Fungsi kthLargestLevelSum menggunakan baris gilir untuk melaksanakan BFS traversal. Untuk setiap tahap, kami menjumlahkan nilai nod dan menyimpan hasilnya dalam tatasusunan ($levelSums).
Isih Jumlah Tahap: Selepas melintasi keseluruhan pokok dan mengira jumlah tahap, kami mengisih jumlah dalam tertib menurun menggunakan rsort. Ini membolehkan kami mengakses jumlah terbesar ke-k dengan mudah.
Pengendalian Kes Tepi: Jika terdapat kurang daripada tahap k, kami kembalikan -1.



  
  
  Kerumitan Masa:




BFS Traversal: O(n), dengan n ialah bilangan nod dalam pepohon.

Isih: O(m log m), dengan m ialah bilangan aras dalam pokok. Memandangkan m jauh lebih kecil daripada n, pengisihan adalah agak pantas.
Kerumitan masa keseluruhan: O(n m log m).



  
  
  Kerumitan Ruang:




Baris gilir: O(n), untuk menyimpan nod semasa BFS.

Jumlah Tahap: O(m), untuk menyimpan jumlah setiap tahap.
Kerumitan ruang keseluruhan: O(n).


Pendekatan ini memastikan bahawa kami melintasi pokok dengan cekap dan mengembalikan jumlah peringkat kke terbesar yang betul.

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 Kth Jumlah Terbesar dalam Pokok Perduaan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!