[LeetCode] 每日一题 1367. 二叉树中的链表

题目链接

题目描述

给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。

如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 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 <= node.val <= 100 。

• 链表包含的节点数目在 1 到 100 之间。

• 二叉树包含的节点数目在 1 到 2500 之间。

题解

解题思路

这道题要求判断一个链表是否为二叉树中某条一直向下路径的子路径，可以通过递归遍历二叉树并进行匹配来解决。具体思路如下：

1. 递归遍历树
   对于二叉树的每一个节点，都可以作为链表匹配的起始点，因此需要通过递归前序遍历树的所有节点

2. 路径匹配
   对于每个树节点，判断从这个节点开始是否存在一条路径与链表匹配。如果当前节点与链表的第一个值相同，则继续递归检查左子树和右子树是否能匹配链表的后续部分

3. 递归结束条件

   • 如果链表已经匹配完成（head == null），说明找到了一条符合条件的路径，返回 true

   • 如果二叉树的当前节点为空（root == null），说明路径中断，返回 false

   • 如果当前树节点值与链表节点值不等，也返回 false

代码实现

class Solution {
    public boolean isSubPath(ListNode head, TreeNode root) {
        // 链表已经匹配完成
        if (head == null) {
            return true;
        }
        // 树遍历到底，链表仍未匹配完成
        if (root == null) {
            return false;
        }
        // 当前节点是否匹配，或者左子树、右子树是否匹配
        return isSamePath(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
    }

    boolean isSamePath(ListNode head, TreeNode root) {
        // 链表匹配完成
        if (head == null) {
            return true;
        }
        // 树的路径中断
        if (root == null) {
            return false;
        }
        // 当前节点值匹配，继续匹配左右子树
        return head.val == root.val && (isSamePath(head.next, root.left) || isSamePath(head.next, root.right));
    }
}

复杂度分析

1. 时间复杂度

   • 最差情况下，需要检查树中每个节点是否作为链表的起点，共有 O(N) 个节点（假设树的节点数为 N）

   • 对于每个起点节点，还可能需要匹配链表的所有节点，复杂度为 O(M)（假设链表的长度为 M）

   • 因此，总时间复杂度为 O(N * M)

2. 空间复杂度

   • 空间主要用于递归调用栈。树的深度为 O(log N)（对于平衡二叉树），链表的深度为 O(M)

   • 因此，空间复杂度为 O(log N + M)

总结

这道题的核心在于递归地判断二叉树中是否存在一条路径与链表完全匹配。通过将递归分解为两部分（路径匹配和遍历树），能够高效地解决问题。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。