1367。二元樹中的鍊錶
難度：中
主題：鍊錶、樹、深度優先搜尋、廣度優先搜尋、二元樹
給定一個二元樹根和一個以頭為第一個節點的鍊錶。
如果鍊錶中從頭開始的所有元素都對應於二元樹中連接的向下路徑，則傳回True，否則回傳False。
在此上下文中，向下路徑是指從某個節點開始並向下的路徑。
範例1：
-
輸入： head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null ,1,3]
-
輸出： true
-
說明：藍色節點構成二元樹中的子路徑。
範例2：
-
輸入： head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null ,null,1,3]
-
輸出： true
範例 3：
-
輸入： head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null ,null,null,1,3]
-
輸出： false
-
解釋： 二元樹中沒有路徑包含從 head 開始的鍊錶的所有元素。
約束：
- 樹中的節點數將在 [1, 2500] 範圍內。
- 清單中的節點數量將在 [1, 100] 範圍內。
-
1
提示：
- 給定鍊錶中的指標和二元樹中的任何節點，建立遞歸函數。檢查鍊錶中從頭開始的所有元素是否對應二元樹中的某個向下路徑。
解：
我們需要遞歸地檢查鍊錶是否可以匹配二元樹中的向下路徑。我們將使用深度優先搜尋 (DFS) 來探索二元樹，並嘗試匹配從頭到葉節點的鍊錶。
我們可以採取以下解決方案：
步驟：
-
匹配鍊錶的遞歸函數：建立一個接受鍊錶節點和樹節點的輔助函數。此函數檢查從目前節點開始的鍊錶是否與二元樹中的向下路徑相符。
-
透過樹進行DFS：使用DFS遍歷二元樹，並在每個節點處檢查是否存在從該節點開始的匹配。
-
基本條件：如果鍊錶已完全遍歷，則遞迴應停止並傳回 true，如果二元樹節點為 null 或值不匹配，則傳回 false。
-
在每個節點開始搜尋：在每個樹節點開始匹配檢查，以找到鍊錶的潛在起點。
讓我們用 PHP 實作這個解：1367。二元樹中的鍊錶
<?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
?>
登入後複製
解釋：
-
isSubPath($head, $root):
- 此函數遞歸地檢查從 $head 開始的鍊錶是否對應於樹中的任何向下路徑。
- 它首先檢查當前根節點是否是列表的開頭（透過呼叫 dfs）。
- 如果沒有，則遞歸搜尋左右子樹。
-
dfs($head, $root):
- 此輔助函數檢查鍊錶是否與從目前樹節點開始的樹相符。
- 如果清單完全遍歷（$head === null），則傳回true。
- 如果樹節點為空或值不匹配，則傳回 false。
- 否則，繼續檢查左右子節點。
執行範例：
對於輸入 head = [4,2,8] 和 root = [1,4,4,null,2,2,null,1,null,6,8]，演算法將：
- 從根節點（節點1）開始，配對失敗。
- 移動到左子節點（節點4），匹配4，然後向下移動並匹配2，然後匹配8，返回true。
複雜：
-
時間複雜度：O(N * min(L, H))，其中N是二元樹的節點數，L是鍊錶的長度，H是二元樹的高度樹。
-
空間複雜度：由於二元樹的遞歸深度，O(H)。
此解決方案使用 DFS 有效檢查二元樹中的子路徑。
聯絡連結
このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!
このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:
以上是二元樹中的鍊錶的詳細內容。更多資訊請關注PHP中文網其他相關文章！
