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.