Topik:
Jumlah jalur maksimum pohon biner
Diberikan pohon biner, temukan jumlah jalur maksimum.
Jalan setapak dapat dimulai dan diakhiri pada simpul apa pun di pohon.
Misalnya:
Mengingat pohon biner di bawah ini,
1 / / 2 3
Kembali 6.
Node mungkin negatif, mencari jalan paling banyak sehingga node yang dilewati adalah yang terbesar. Jalur dapat dimulai dan berakhir di simpul apa pun tetapi tidak bisa kembali.
Meskipun pertanyaan ini terlihat tidak biasa, jika Anda memikirkannya, Anda akan menemukan bahwa itu tidak lebih dari traversal pohon biner + ide perencanaan dinamis sederhana.
Kita dapat memisahkan masalah: bahkan jika jalur terbesar terakhir tidak melewati simpul root, itu harus memiliki "titik tertinggi" sendiri. Oleh karena itu, kita hanya perlu mencari tahu untuk semua node: jika jalur mengambil node ini sebagai "titik tertinggi", berapa panjang maksimum jalur? Catatan sebagai maks. Kemudian temukan nilai maksimum maks dalam maksimal, yang merupakan hasil yang Anda cari. Gagasan yang sama seperti "menemukan selanjutnya kontinu terbesar dalam urutan integer".
Berikut ini adalah menemukan hubungan antara maks yang sesuai dengan masing -masing "titik tertinggi".
Mari kita ambil node root sebagai contoh. Metode perhitungan untuk jalur maksimum yang melewati simpul root adalah:
Kami menemukan panjang jalur maksimum A di subtree kiri dengan anak kiri sebagai titik awal, dan panjang jalur maksimum B di subtree kanan dengan anak kanan sebagai titik awal. Kemudian max = maks dari titik ini (a+b+node.val, a+node.val, b+node.val, node.val)
Oleh karena itu, kami mendefinisikan fungsi untuk menghitung A atau B di atas. Parameternya adalah sebuah simpul, dan nilai pengembaliannya adalah panjang jalur maksimum. Namun, titik awal jalur ini harus berupa node input, dan jalur harus pada subtree dengan titik awal sebagai simpul root.
Maka nilai pengembalian fungsi fungsi (node) dapat didefinisikan sebagai berikut: returnmax (func (node.left)+node.val, func (node.right)+node.val, node.val)
Kondisi terminasi adalah node == null, dan mengembalikan 0 secara langsung.
Kemudian kami menemukan bahwa proses menghitung max di atas dan menghitung max dapat sepenuhnya dimasukkan ke dalam func (node).
Menurut kode ide ini, MaxPathSumCore adalah implementasi Func (Node) di atas:
/** * Definisi untuk pohon biner * struct treenode { * int val; * Treeenode * kiri; * Treenode * benar; * Treenode (int x): val (x), kiri (null), kanan (null) {} *}; */solusi kelas {public: int maxpathsum (treenode *root) {maxpathsumcore (root); return max;} int maxpathsumcore (node *treenode) {if (null == node) return 0; int a = maxpathsumCore (node -> kiri); int b = maxpathsumeum (node -node) (node) (node -> kiri); int b = maxpathsumeum (node -node) (node) (node -> kiri); int b = maxpathsumeM > MAX) MAX = (a+b+node->val);if((a+node->val) > MAX) MAX = (a+node->val);if((b+node->val) > MAX) MAX = (b+node->val);if(node->val > MAX) MAX = node->val;int maxViaThisNode = ((a + node->val) > node->val ? (a + node-> val): node-> val); return (maxviathisnode> (b + node-> val)? maxviathisnode: (b + node-> val));} private: int max = -9999999;};Kompleksitas waktu o (n), n adalah jumlah total node.
Meringkaskan
Di atas adalah seluruh konten artikel ini tentang analisis kode dari jalur maksimum pohon biner dalam pemrograman Java. Saya harap ini akan membantu semua orang. Teman yang tertarik dapat terus merujuk ke topik terkait lainnya di situs ini. Jika ada kekurangan, silakan tinggalkan pesan untuk menunjukkannya. Terima kasih teman atas dukungan Anda untuk situs ini!