LeetCode 题解工作台
二叉树中的链表
给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。 如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。 一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。 示…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 链表指针操作
答案摘要
我们设计一个递归函数 $dfs(head, root)$，表示链表 是否是以 为起点的路径上的节点值一一对应的子路径。函数 $dfs(head, root)$ 的逻辑如下： - 如果链表 为空，说明链表已经遍历完了，返回 `true`；
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
给你一棵以 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之间。
解题思路
方法一：递归
我们设计一个递归函数 ，表示链表 是否是以 为起点的路径上的节点值一一对应的子路径。函数 的逻辑如下：
- 如果链表 为空，说明链表已经遍历完了，返回
true； - 如果二叉树 为空，说明二叉树已经遍历完了，但链表还没遍历完，返回
false； - 如果二叉树 的值与链表 的值不相等，返回
false； - 否则，返回 或 。
我们在主函数中，对二叉树的每个节点调用 ，只要有一个返回 true，就说明链表是二叉树的子路径，返回 true；如果所有节点都返回 false，说明链表不是二叉树的子路径，返回 false。
时间复杂度 。其中 是二叉树的节点数。
# 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: Optional[ListNode], root: Optional[TreeNode]) -> bool:
def dfs(head, root):
if head is None:
return True
if root is None or root.val != head.val:
return False
return dfs(head.next, root.left) or dfs(head.next, root.right)
if root is None:
return False
return (
dfs(head, root)
or self.isSubPath(head, root.left)
or self.isSubPath(head, root.right)
)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(2^{k - 1} * m), where k is the depth of tree and m is the list length, due to potentially exploring both subtrees at each tree node. Space complexity is O(n + m) accounting for tree recursion stack and linked list traversal. |
| 空间 | O(n + m) |
面试官常问的追问
外企场景- question_mark
Focus on traversing both structures simultaneously and maintaining list node alignment.
- question_mark
Consider early termination when a mismatch occurs along a path.
- question_mark
Check edge cases where the linked list starts at leaf nodes or the root.
常见陷阱
外企场景- error
Failing to start matching at every tree node rather than only at the root.
- error
Incorrectly assuming list nodes can skip tree nodes; all nodes must be consecutive downward.
- error
Ignoring tree null branches, leading to null pointer exceptions during recursion.
进阶变体
外企场景- arrow_right_alt
Check if a circular linked list can be matched along a downward path in a tree.
- arrow_right_alt
Determine the longest linked list prefix that matches any path in a binary tree.
- arrow_right_alt
Find all paths in the binary tree that exactly match the given linked list sequence.