バイナリ ツリーのリンク リスト

1367年。バイナリツリーのリンクリスト

難易度: 中

トピック: リンクリスト、ツリー、深さ優先検索、幅優先検索、バイナリツリー

バイナリ ツリーのルートと、最初のノードとして head を持つリンク リストが与えられます。

先頭から始まるリンクリスト内のすべての要素がバイナリツリーで接続されている下向きのパスに対応する場合は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
• 説明: 先頭からのリンク リストのすべての要素を含むパスがバイナリ ツリーにありません。

制約:

• ツリー内のノードの数は [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 を返します。
   • ツリー ノードが null であるか、値が一致しない場合は、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 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上がバイナリ ツリーのリンク リストの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。