LeetCode 1367. 二叉树中的链表

题目描述
给你一棵以 root 为根的二叉树和一个以 head 为开头的单向链表。如果在二叉树中，存在一条向下的路径，其路径上的节点值依次与链表中每个节点的值相等，请你返回 True ，否则返回 False。
这里的“向下”路径是指：从树中某个节点开始，通过连续向子节点（只能从父节点指向左子节点或右子节点）移动形成的路径。

换句话说，你需要判断：能否在二叉树中找到一条从某个节点开始向下（只能从父节点到子节点方向）的路径，使得路径上的节点值按顺序恰好等于链表从头到尾的所有节点值。

注意：

• 二叉树和链表中的节点数目范围分别是 [1, 2500]。
• 链表的节点值、二叉树的节点值均为整数，范围是 [1, 100]。

解题过程

第一步：理解核心匹配规则
这个问题的核心是判断链表的连续序列是否对应于二叉树中从上到下（不能向上或跳跃）的一条路径。
例如：

链表: 1 -> 4 -> 2 -> 8
二叉树片段：
        1
       / \
      4   3
     / \   \
    1   2   5
       /
      8

从二叉树的根节点（值为1）开始，走“左子节点4 -> 右子节点2 -> 左子节点8”，这条路径的值序列恰好是链表序列，因此返回 True。

第二步：分解问题
我们需要在二叉树中尝试以每个节点作为“匹配起点”，然后从该起点开始，判断能否匹配整个链表。
因此可以分解为两个子任务：

1. 遍历二叉树的每个节点（作为可能的匹配起点）。
2. 对每个起点，尝试匹配链表。

这提示我们可以用树的遍历（递归DFS）来完成：

• 外层递归：遍历二叉树所有节点（前序、中序、后序均可，常用前序）。
• 内层递归：给定二叉树当前节点和链表当前节点，判断从该树节点开始是否能匹配链表的剩余部分。

第三步：设计递归匹配函数
定义一个递归函数 match(tree_node, list_node)：

• 如果 list_node 为空，表示链表已经全部匹配完，返回 True。
• 如果 tree_node 为空，表示二叉树节点不足，但链表还有剩余，返回 False。
• 如果 tree_node.val != list_node.val，当前节点不匹配，返回 False。
• 如果当前节点值匹配，则我们需要继续匹配链表的下一个节点，但二叉树可以走左子树或右子树，所以递归调用：
  • match(tree_node.left, list_node.next) 或
  • match(tree_node.right, list_node.next)
    只要有一条子树路径能匹配剩余的链表，就成功。

第四步：在二叉树中尝试每个起点
从二叉树的根节点开始，用前序遍历依次以每个节点为起点调用上述 match 函数。
具体地，我们可以写一个主函数 isSubPath(head, root)：

1. 如果 root 为空，返回 False。
2. 以当前 root 为起点，尝试匹配整个链表（调用 match(root, head)），如果成功返回 True。
3. 否则，递归地在左子树和右子树中寻找起点：
   • 检查 isSubPath(head, root.left)
   • 检查 isSubPath(head, root.right)
     只要有一边成功，就返回 True。

第五步：举例推演
以示例为例：
链表：1 -> 4 -> 2 -> 8
二叉树：

        1
       / \
      4   3
     / \   \
    1   2   5
       /
      8

1. 从根节点 1 开始尝试匹配：
   • 匹配链表节点 1：值相等。
   • 递归匹配链表下一个 4，在树中尝试走左子节点 4，匹配。
   • 递归匹配链表下一个 2，在树中尝试走 4 的右子节点 2，匹配。
   • 递归匹配链表下一个 8，在树中尝试走 2 的左子节点 8，匹配。
   • 链表结束，返回 True。
     因此最终结果为 True。

第六步：时间复杂度分析
设二叉树节点数为 N，链表长度为 M。
最坏情况下，我们需要以每个树节点为起点尝试匹配，每次匹配最多进行 M 次比较（因为一旦某个节点不匹配就会停止）。
因此最坏时间复杂度为 O(N * M)。
由于节点数最多 2500，这是可接受的。

第七步：代码实现（Python）

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        # 递归匹配函数
        def match(tree_node, list_node):
            if not list_node:  # 链表全部匹配完
                return True
            if not tree_node:  # 树节点不够
                return False
            if tree_node.val != list_node.val:  # 值不匹配
                return False
            # 当前节点匹配，继续匹配链表下一个节点
            return match(tree_node.left, list_node.next) or match(tree_node.right, list_node.next)
        
        # 主函数遍历每个树节点作为起点
        if not root:
            return False
        # 以当前 root 为起点尝试匹配
        if match(root, head):
            return True
        # 否则在左右子树中寻找起点
        return self.isSubPath(head, root.left) or self.isSubPath(head, root.right)

第八步：思考优化
以上解法直观清晰。我们还可以用 KMP 思路优化，但鉴于本题数据规模不大，上述解法已足够。注意避免重复计算：这里没有重叠子问题，所以不需要记忆化。

总结
本题的关键是将问题分解为“尝试每个树节点作为起点”和“从该起点匹配链表”两部分，并用两个递归函数分别处理。在匹配过程中，由于链表是单向的，我们只需在树中向下匹配，直到链表结束或树节点不匹配。