Linked List in Binary Tree Python Solution

lcpy gen -n 1367   # by problem number
lcpy gen -s linked_list_in_binary_tree   # by problem name

Input: head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
Explanation: Nodes in blue form a subpath in the binary Tree.

Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true

Input: head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: false
Explanation: There is no path in the binary tree that contains all the elements of the linked list from head.

from leetcode_py import ListNode, TreeNode


class Solution:
    # Time: O(n * m) worst case (n tree nodes, m list length)
    # Space: O(h) recursion depth
    def is_sub_path(self, head: ListNode[int] | None, root: TreeNode[int] | None) -> bool:
        if root is None:
            return False

        def match(node: TreeNode[int] | None, cur: ListNode[int] | None) -> bool:
            if cur is None:
                return True
            if node is None or node.val != cur.val:
                return False
            return match(node.left, cur.next) or match(node.right, cur.next)

        def dfs(node: TreeNode[int] | None) -> bool:
            if node is None:
                return False
            return match(node, head) or dfs(node.left) or dfs(node.right)

        return dfs(root)