二元樹中的鍊錶

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

提示：

1. 給定鍊錶中的指標和二元樹中的任何節點，建立遞歸函數。檢查鍊錶中從頭開始的所有元素是否對應二元樹中的某個向下路徑。

解：

我們需要遞歸地檢查鍊錶是否可以匹配二元樹中的向下路徑。我們將使用深度優先搜尋 (DFS) 來探索二元樹，並嘗試匹配從頭到葉節點的鍊錶。

我們可以採取以下解決方案：

步驟：

1. 匹配鍊錶的遞歸函數：建立一個接受鍊錶節點和樹節點的輔助函數。此函數檢查從目前節點開始的鍊錶是否與二元樹中的向下路徑相符。
2. 透過樹進行DFS：使用DFS遍歷二元樹，並在每個節點處檢查是否存在從該節點開始的匹配。
3. 基本條件：如果鍊錶已完全遍歷，則遞迴應停止並傳回 true，如果二元樹節點為 null 或值不匹配，則傳回 false。
4. 在每個節點開始搜尋：在每個樹節點開始匹配檢查，以找到鍊錶的潛在起點。

讓我們用 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
?>

解釋：

1. isSubPath($head, $root):

   • 此函數遞歸地檢查從 $head 開始的鍊錶是否對應於樹中的任何向下路徑。
   • 它首先檢查當前根節點是否是列表的開頭（透過呼叫 dfs）。
   • 如果沒有，則遞歸搜尋左右子樹。

2. 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 で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上是二元樹中的鍊錶的詳細內容。更多資訊請關注PHP中文網其他相關文章！