NeetCode #432LC-1367MediumTrees
← Back to All Problems#432 · #1367 · Linked List in Binary Tree(二叉树中的链表)
📌 Problem Statement & Constraints
Given a binary tree
root and a linked list head, return true if the list's values form a downward path in the tree. Constraints: the number of nodes in the tree is in [1, 2500], in the list in [1, 100], 1 <= Node.val <= 100.💡 Core Algorithmic Approaches
- For every tree node, test whether a downward path starting there matches the list.
- The match helper advances both the tree node and the list pointer; a match succeeds when the list is exhausted.
- If the match fails at the current node, try starting from either child.
- The worst case is O(n * m), which the constraints allow.
💻 Benchmark Python3 Implementation
class Solution:
def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
def match(node: Optional[TreeNode], cur: Optional[ListNode]) -> bool:
if not cur:
return True # the whole list was matched
if not node:
return False # the path ended too early
if node.val != cur.val:
return False
# continue downward along either child
return match(node.left, cur.next) or match(node.right, cur.next)
if not root:
return False
return (match(root, head)
or self.isSubPath(head, root.left)
or self.isSubPath(head, root.right))⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n * m): each tree node may start a match attempt costing O(m).
💾 Space Complexity
O(h + m) for the recursion stacks.
⚠️ Interview Pitfalls & Follow-ups
- Checking
curbeforenode: if the list is exhausted the match succeeds even at aNonetree node, so the order matters. - Requiring the path to start at the root: it may start anywhere, hence the outer recursion.
- Only following the left child: both children must be tried.
- Confusing this with a subtree match: the list follows a single downward path, not a branching structure.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Trees Problems
中文速览与面试要点
二叉树中的链表
给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。如果在二叉树中,存在一条一直向下的路径,且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值,那么请你返回 True,否则返回 False。一直向下的路径的意思是:从树中某个节点开始,一直连续向下的路径。约束:二叉树和链表中的每个节点的值都满足 1 ≤ Node.val ≤ 100;链表包含的节点数目在 1 到 100 之间;二叉树包含的节点数目在 1 到 2500 之间。
核心要点
- 双重递归(标准解) :外层遍历树的每个节点作为路径起点;内层从该起点开始,同时沿链表和树向下匹配。
- 内层匹配逻辑 :若链表已走完则返回 True;若树节点为空或值不等则返回 False;否则递归匹配 (ln.next, tn.left) 与 (ln.next, tn.right) 。
- 为什么用「或」连接左右 :路径可以走左也可以走右,任一成功即可。
- 复杂度 :O(n · m)。n 为树节点数、m 为链表长度(m ≤ 100,n ≤ 2500,可接受)。
常见陷阱
- 只尝试从根节点开始匹配 :路径可以从任意节点开始,必须遍历所有节点作为起点。
- 匹配失败后不尝试其他起点 :必须用 or 连接「当前起点」与「子节点起点」。
- 内层匹配只走一条分支 :路径可以向左或向右,必须用 or 连接。
- 链表走完但树节点也走完 :此时应返回 True(链表走完即成功),本解的第一个判断已覆盖。
参考实现
class Solution:
def isSubPath(self, head: 'ListNode', root: 'TreeNode') -> bool:
def match(ln, tn) -> bool:
"""从 tn 开始匹配链表 ln。"""
if not ln:
return True # 链表走完 -> 匹配成功
if not tn:
return False
if ln.val != tn.val:
return False
return match(ln.next, tn.left) or match(ln.next, tn.right)
if not root:
return False
return (match(head, root) # 以当前节点为起点
or self.isSubPath(head, root.left)
or self.isSubPath(head, root.right))