力扣1367：二叉树中查找链表路径-编程实验室

问题解构

力扣第1367题“二叉树中的列表”要求判断一个给定的链表是否在二叉树中作为一条自上而下的路径存在。这意味着需要在二叉树中寻找一条路径，其节点值依次与链表节点的值完全匹配，且路径方向必须是从父节点到子节点（可以跳过中间节点，但方向必须一致）。

核心约束：

链表节点值必须与二叉树路径节点值顺序、值完全一致。
路径必须是自上而下的，即从某个二叉树节点开始，只能向子节点方向移动（左子或右子）。
链表可以是二叉树路径的一部分，即链表结束时，二叉树路径可以还有后续节点（题目要求链表是路径的“一部分”，但根据常见理解及测试用例，通常要求路径节点数至少等于链表长度，且值序列完全匹配链表。更严谨地说，是判断二叉树中是否存在一条从上到下的路径，其节点值的顺序与链表节点的值顺序完全相同）。

方案推演

解决此问题通常采用深度优先搜索（DFS）配合递归的策略。核心思路是遍历二叉树的每个节点，并以该节点为起点，尝试匹配整个链表。

可以设计两个递归函数：

主递归函数dfs(root, head)：遍历二叉树，对每个节点，调用辅助函数判断是否从该节点开始能匹配链表。
辅助递归函数isSubPath(head, root)：判断从当前二叉树节点root开始，是否能匹配以head开头的链表。

递归终止条件：

如果链表指针head为空，说明链表已全部匹配完成，返回true。
如果二叉树节点root为空，但链表节点还有剩余，说明路径已无法继续，返回false。
如果当前二叉树节点值root.val不等于链表节点值head.val，则从当前起点匹配失败，返回false。

递归过程：
在辅助函数中，若当前节点值匹配，则继续递归判断左子树或右子树是否能匹配链表的下一个节点。在主函数中，需要检查当前节点为起点是否能匹配，或者左/右子树中是否存在匹配。

代码实现

以下是基于上述思路的 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: """ 主函数：判断链表head是否在二叉树root中作为一条自上而下的路径存在。 """ if not head: return True # 空链表视为存在于任何树中 if not root: return False # 空树不可能包含非空链表 # 以当前root为起点尝试匹配，或在左/右子树中继续寻找起点 return self.dfs(head, root) or \ self.isSubPath(head, root.left) or \ self.isSubPath(head, root.right) def dfs(self, head: ListNode, root: TreeNode) -> bool: """ 辅助函数：判断从二叉树节点root开始，是否能匹配以head开头的链表。 """ # 链表已全部匹配完成 if not head: return True # 二叉树节点为空，无法继续匹配 if not root: return False # 当前节点值不匹配，失败 if head.val != root.val: return False # 当前节点匹配成功，继续匹配链表的下一个节点与当前节点的左子节点或右子节点 return self.dfs(head.next, root.left) or self.dfs(head.next, root.right)

算法解析

时间复杂度分析

最坏情况下，需要遍历二叉树的每个节点（N个），对每个节点都可能执行一次dfs匹配，而dfs匹配的长度最多为链表长度M。
因此，最坏时间复杂度为O(N × M)，其中 N 是二叉树节点数，M 是链表长度。
平均情况会好于最坏情况，因为并非每个节点都需要完整匹配整个链表。

空间复杂度分析

空间复杂度主要取决于递归调用栈的深度。
在最坏情况下（树退化为链表），递归深度为N，因此空间复杂度为O(N)。

关键点说明

双重递归：主函数isSubPath用于遍历二叉树寻找匹配起点，辅助函数dfs用于从特定起点开始匹配链表，两者结合覆盖了所有可能的路径起点和匹配过程。
匹配方向：dfs函数中只向root.left和root.right递归，保证了路径是自上而下的，不会回溯到父节点。
短路优化：主函数中使用or连接三个递归调用，利用短路特性，一旦找到匹配立即返回true，减少不必要的计算。

示例演示

假设链表为1 -> 4 -> 2 -> 6，二叉树如下：

1 / \ 4 4 / \ \ 1 2 6 / / \ \ 8 1 3 7

匹配过程：

从根节点1开始匹配，链表头1匹配成功，进入dfs。
dfs(4, 节点4)：链表节点4与二叉树左子节点4匹配成功。
dfs(2, 节点2)：链表节点2与二叉树节点2匹配成功。
dfs(6, 节点6)：链表节点6与二叉树节点6匹配成功。
链表结束，返回true。

因此，该链表存在于二叉树中作为一条路径（路径为1 -> 4 -> 2 -> 6）。

边界情况处理

边界情况	处理方式	说明
链表为空	直接返回`true`	空链表视为存在于任何树中
二叉树为空	直接返回`false`	空树不可能包含非空链表
链表节点值不匹配	当前起点匹配失败，尝试其他起点	在`dfs`中立即返回`false`，主函数尝试其他分支
链表长度大于路径深度	匹配失败	`dfs`中二叉树节点先于链表变为空时返回`false`

与其他相似问题的对比

题目	核心问题	解法差异	关键点
1367. 二叉树中的列表	判断链表是否为二叉树中自上而下的路径	双重递归，匹配链表节点序列	路径必须连续向下，值顺序严格匹配
面试题 04.10. 检查子树	判断一棵树是否为另一棵树的子树	递归比较树结构（节点值和左右子树）	需要整个子树结构完全一致，包括所有后代节点
572. 另一棵树的子树	类似上题，判断子树	相同，递归比较树结构	子树必须从某个节点开始完全匹配