. Flip Pokok Binari Setara

951. Balikkan Pokok Binari Setara

Kesukaran: Sederhana

Topik: Pokok, Carian Pertama Kedalaman, Pokok Binari

Untuk pokok binari T, kita boleh mentakrifkan operasi flip seperti berikut: pilih mana-mana nod dan tukar subpokok anak kiri dan kanan.

Pokok perduaan X ialah setara dengan pokok perduaan Y jika dan hanya jika kita boleh membuat X sama dengan Y selepas beberapa operasi flip.

Memandangkan akar dua pokok binari root1 dan root2, kembalikan

benar jika kedua-dua pokok itu setara flip atau palsu sebaliknya.

Contoh 1:

• Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5 ,null,null,null,null,8,7]
• Output: benar
• Penjelasan: Kami menyelak nod dengan nilai 1, 3 dan 5.

Contoh 2:

• Input: root1 = [], root2 = []
• Output: benar

Contoh 3:

• Input: root1 = [], root2 = [1]
• Output: palsu

Kekangan:

Bilangan nod dalam setiap pokok adalah dalam julat [0, 100].
Setiap pokok akan mempunyai nilai nod unik dalam julat [0, 99].

Penyelesaian:

Kami boleh menggunakan carian mendalam-pertama (DFS) rekursif. Ideanya ialah dua pokok adalah setara flip jika nilai akarnya adalah sama dan subpokok sama ada sama (tanpa sebarang lambungan) atau ia menjadi sama selepas membalikkan anak kiri dan kanan pada beberapa nod.

Pelan:

1. Kes Asas:

   Jika kedua-dua root1 dan root2 adalah nol, ia adalah setara flip secara remeh.
   Jika hanya satu daripadanya adalah batal, ia tidak boleh setara.
   Jika nilai punca root1 dan root2 berbeza, ia tidak boleh setara.

2. Kes Rekursif:

   Semak dua kemungkinan secara rekursif:
   • Subpokok kiri root1 adalah flip bersamaan dengan subpokok kiri akar2, dan subpokok kanan root1 adalah flip bersamaan dengan subpokok kanan root2 (iaitu, tiada flip).
     Subpokok kiri root1 adalah flip bersamaan dengan subtree kanan root2, dan subtree kanan root1 adalah flip bersamaan dengan subtree kiri root2 (iaitu, flip anak).

Mari laksanakan penyelesaian ini dalam PHP:

951. Balikkan Pokok Binari Setara

<?php
// Definition for a binary tree node.
class TreeNode {
    public $val;
    public $left;
    public $right;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

/**
 * @param TreeNode $root1
 * @param TreeNode $root2
 * @return Boolean
 */
function flipEquiv($root1, $root2) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$root1 = new TreeNode(1,
    new TreeNode(2, new TreeNode(4), new TreeNode(5, new TreeNode(7), new TreeNode(8))),
    new TreeNode(3, new TreeNode(6), null)
);

$root2 = new TreeNode(1,
    new TreeNode(3, null, new TreeNode(6)),
    new TreeNode(2, new TreeNode(4), new TreeNode(5, new TreeNode(8), new TreeNode(7)))
);

var_dump(flipEquiv($root1, $root2)); // Output: bool(true)
?>

Penjelasan:

1. Kelas TreeNode: Kelas TreeNode mewakili nod dalam pepohon binari, dengan pembina untuk memulakan nilai nod, anak kiri dan anak kanan.

2. FlipEquivFungsi:

   • Kes asas mengendalikan apabila kedua-dua nod adalah batal, apabila satu adalah batal atau apabila nilai tidak sepadan.
   • Kes rekursif menyemak kedua-dua kemungkinan (tiada flip vs. flip), memastikan subpohon adalah setara flip di bawah mana-mana keadaan.

Kerumitan Masa:

• Fungsi memeriksa setiap nod dalam kedua-dua pepohon dan setiap panggilan rekursif memproses dua subpohon. Oleh itu, kerumitan masa ialah O(N), dengan N ialah bilangan nod dalam pepohon.

Kerumitan Ruang:

• Kerumitan ruang ialah O(H), dengan H ialah ketinggian pokok, kerana timbunan rekursif. Dalam kes yang paling teruk (untuk pokok senget), ini mungkin O(N).

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 . Flip Pokok Binari Setara. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!