Senarai Berpaut dalam Pokok Binari

1367. Senarai Terpaut dalam Pokok Binari

Kesukaran: Sederhana

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

Diberikan akar pokok binari dan senarai terpaut dengan kepala sebagai nod pertama.

Kembali Benar jika semua elemen dalam senarai terpaut bermula dari kepala sepadan dengan beberapa laluan ke bawah yang disambungkan dalam pepohon binari sebaliknya kembalikan Salah.

Dalam konteks ini laluan ke bawah bermaksud laluan yang bermula pada beberapa nod dan pergi ke bawah.

Contoh 1:

• Input: kepala = [4,2,8], akar = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null ,1,3]
• Output: benar
• Penjelasan: Nod berwarna biru membentuk sublaluan dalam Pokok binari.

Contoh 2:

• Input: kepala = [1,4,2,6], akar = [1,4,4,null,2,2,null,1,null,6,8,null,null,null ,null,1,3]
• Output: benar

Contoh 3:

• Input: kepala = [1,4,2,6,8], punca = [1,4,4,null,2,2,null,1,null,6,8,null,null ,null,null,1,3]
• Output: palsu
• Penjelasan: Tiada laluan dalam pepohon binari yang mengandungi semua elemen senarai terpaut dari kepala.

Kekangan:

• Bilangan nod dalam pepohon akan berada dalam julat [1, 2500].
• Bilangan nod dalam senarai akan berada dalam julat [1, 100].
• 1

Petunjuk:

1. Buat fungsi rekursif, diberikan penunjuk dalam Senarai Terpaut dan sebarang nod dalam Pokok Binari. Semak sama ada semua elemen dalam senarai terpaut bermula dari kepala sepadan dengan beberapa laluan ke bawah dalam pepohon binari.

Penyelesaian:

Kita perlu menyemak secara rekursif sama ada senarai terpaut boleh memadankan laluan ke bawah dalam pepohon binari. Kami akan menggunakan carian depth-first (DFS) untuk meneroka pepohon binari dan cuba memadankan senarai terpaut dari kepala ke nod daun.

Begini cara kita boleh mendekati penyelesaian:

Langkah-langkah:

1. Fungsi rekursif untuk memadankan senarai terpaut: Buat fungsi pembantu yang mengambil nod senarai terpaut dan nod pokok. Fungsi ini menyemak sama ada senarai terpaut bermula dari nod semasa sepadan dengan laluan ke bawah dalam pepohon binari.
2. DFS melalui pepohon: Lintas pepohon binari menggunakan DFS, dan pada setiap nod, semak sama ada terdapat padanan bermula dari nod itu.
3. Syarat asas: Rekursi harus berhenti dan kembali benar jika senarai terpaut dilalui sepenuhnya dan kembali palsu jika nod pokok binari adalah batal atau nilai tidak sepadan.
4. Mulakan carian pada setiap nod: Mulakan semakan padanan di setiap nod pokok untuk mencari titik permulaan yang berpotensi untuk senarai terpaut.

Mari laksanakan penyelesaian ini dalam PHP: 1367. Senarai Terpaut dalam Pokok Binari

<?php // Definition for a singly-linked list node.
class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

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

class Solution {

    /**
     * @param ListNode $head
     * @param TreeNode $root
     * @return Boolean
     */
    function isSubPath($head, $root) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    // Helper function to match the linked list starting from the current tree node.
    function dfs($head, $root) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

// Example usage:

// Linked List: 4 -> 2 -> 8
$head = new ListNode(4);
$head->next = new ListNode(2);
$head->next->next = new ListNode(8);

// Binary Tree:
//      1
//     / \
//    4   4
//     \   \
//      2   2
//     / \ / \
//    1  6 8  8
$root = new TreeNode(1);
$root->left = new TreeNode(4);
$root->right = new TreeNode(4);
$root->left->right = new TreeNode(2);
$root->right->left = new TreeNode(2);
$root->left->right->left = new TreeNode(1);
$root->left->right->right = new TreeNode(6);
$root->right->left->right = new TreeNode(8);
$root->right->left->right = new TreeNode(8);

$solution = new Solution();
$result = $solution->isSubPath($head, $root);
echo $result ? "true" : "false"; // Output: true
?>

Penjelasan:

1. isSubPath($head, $root):

   • Fungsi ini menyemak secara rekursif sama ada senarai terpaut bermula dari $head sepadan dengan mana-mana laluan ke bawah dalam pepohon.
   • Ia mula-mula menyemak sama ada nod akar semasa ialah permulaan senarai (dengan memanggil dfs).
   • Jika tidak, ia mencari secara rekursif subpokok kiri dan kanan.

2. dfs($kepala, $akar):

   • Fungsi pembantu ini menyemak sama ada senarai terpaut sepadan dengan pepohon bermula pada nod pepohon semasa.
   • Jika senarai dilalui sepenuhnya ($head === null), ia kembali benar.
   • Jika nod pokok adalah batal atau nilai tidak sepadan, ia mengembalikan palsu.
   • Kalau tak, terus check anak kiri kanan.

Contoh Pelaksanaan:

Untuk kepala input = [4,2,8] dan punca = [1,4,4,null,2,2,null,1,null,6,8], algoritma akan:

• Mulakan pada akar (nod 1), gagal padan.
• Bergerak ke anak kiri (nod 4), padankan 4, kemudian bergerak ke bawah dan padankan 2, kemudian padankan 8, kembali benar.

Kerumitan:

• Kerumitan Masa: O(N * min(L, H)), dengan N ialah bilangan nod dalam pokok binari, L ialah panjang senarai terpaut dan H ialah ketinggian binari pokok.
• Kerumitan Angkasa: O(H) disebabkan oleh kedalaman rekursi pokok binari.

Penyelesaian ini dengan cekap memeriksa laluan kecil dalam pepohon binari menggunakan DFS.

Pautan Kenalan

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

Atas ialah kandungan terperinci Senarai Berpaut dalam Pokok Binari. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!