⚡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

中文速览与面试要点

二叉树中的链表

给你一棵以 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))