⚡Flashcard Drill➔
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

  1. For every tree node, test whether a downward path starting there matches the list.
  2. The match helper advances both the tree node and the list pointer; a match succeeds when the list is exhausted.
  3. If the match fails at the current node, try starting from either child.
  4. 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 cur before node: if the list is exhausted the match succeeds even at a None tree 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems