1367.二叉树中的链表

链接：1367.二叉树中的链表
难度：Medium
标签：树、深度优先搜索、链表、二叉树
简介：给你一棵以  root  为根的二叉树和一个  head  为第一个节点的链表。如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以  head  为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。

题解 1 - typescript

• 编辑时间：2021-07-29
• 执行用时：84ms
• 内存消耗：45MB
• 编程语言：typescript
• 解法介绍：dfs 递归遍历。

function isSubPath(head: ListNode | null, root: TreeNode | null): boolean {
  if (head === null) return true;
  if (root === null) return false;
  if (head.val === root.val && find(head, root)) return true;
  return isSubPath(head, root.left) || isSubPath(head, root.right);
  function find(head: ListNode | null, root: TreeNode | null): boolean {
    if (head === null) return true;
    if (root === null) return false;
    if (head.val !== root.val) return false;
    return find(head.next, root.left) || find(head.next, root.right);
  }
}

题解 2 - python

• 编辑时间：2024-12-30
• 执行用时：64ms
• 内存消耗：36.8MB
• 编程语言：python
• 解法介绍：dfs

class Solution:
    @cache
    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode], init: bool = True) -> bool:
        if init: self.head = head
        if head == None: return True
        if root == None: return False
        if head.val == root.val and (self.isSubPath(head.next, root.left, False) or self.isSubPath(head.next, root.right, False)): return True
        return self.isSubPath(self.head, root.left, False) or self.isSubPath(self.head, root.right, False)