二叉树中的链表

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에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이런 유용한 콘텐츠를 더 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

以上是二叉树中的链表的详细内容。更多信息请关注PHP中文网其他相关文章！