Rumah > Artikel > pembangunan bahagian belakang > 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:
Contoh 2:
Contoh 3:
Kekangan:
Petunjuk:
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:
Mari laksanakan penyelesaian ini dalam PHP: 1367. Senarai Terpaut dalam Pokok Binari
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:
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.
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:
Penyelesaian ini dengan cekap memeriksa laluan kecil dalam pepohon binari menggunakan DFS.
Pautan Kenalan
如果您發現本系列有幫助,請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子? 。您的支持對我來說意義重大!
如果您想要更多類似的有用內容,請隨時關注我:
Atas ialah kandungan terperinci Senarai Berpaut dalam Pokok Binari. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!