Given a binary tree root and a linked list with head as the first node. 
Return True if all the elements in the linked list starting from the head correspond to some downward path connected in the binary tree otherwise return False.
In this context downward path means a path that starts at some node and goes downwards.
 
Example 1:

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.  

Example 2:

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

Example 3:
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.

 
Constraints:

1 <= node.val <= 100 for each node in the linked list and binary tree.
The given linked list will contain between 1 and 100 nodes.
The given binary tree will contain between 1 and 2500 nodes.

Difficulty: interview

Starter code:

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
    self.val = val
    self.next = next
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        

Solutions:
class Solution(object):
    def isSubPath(self, h, r0):
        h_vals = []
        while h:
            h_vals.append(str(h.val))
            h = h.next
        h_str = ('-'.join(h_vals)) + '-'  # serialized list

        st = [(r0, '-')]  # DFS stack

        while st:
            r, pre = st.pop()
            if not r:
                continue

            pre = pre + str(r.val) + '-'
            if pre.endswith(h_str):
                return True

            st.append((r.left, pre))
            st.append((r.right, pre))

        return False

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        arr = []
        while head:
            arr.append(head.val)
            head = head.next
        
        t = [-1]
        pos, cnd = 1, 0
        while pos < len(arr):
            if arr[pos] == arr[cnd]:
                t.append(t[cnd])
            else:
                t.append(cnd)
                cnd = t[cnd]
                while cnd >= 0 and arr[pos] != arr[cnd]:
                    cnd = t[cnd]
            pos += 1
            cnd += 1
        t.append(cnd)
        
        def dfs(root, i):
            if i == len(arr):
                return True
            if root is None:
                return False
            while i >= 0 and root.val != arr[i]:
                i = t[i]
            return dfs(root.left, i+1) or dfs(root.right, i+1)

        return dfs(root, 0)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        def dfs(root, head):
            if not root and not head: return True
            if not head and root: return True
            if not root and head: return False
            if root.val != head.val: return False
            left = dfs(root.left, head.__next__)
            right = dfs(root.right, head.__next__)
            return left or right
        
        if not root: return False
        if dfs(root, head): return True
        return self.isSubPath(head, root.left) or self.isSubPath(head, root.right)
            


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        # find the beginning of list node in tree. then traverse
        def helper(lNode, TNode):
            if not lNode:
                return True
            if not TNode:
                return False
            return TNode.val == lNode.val and (
                helper(lNode.next, TNode.left) or helper(lNode.next, TNode.right)
            )
        
        if not head:
            return True
        if not root:
            return False
        return helper(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        def dfs(p,q):
            if not p:
                return True
            if not q or p.val!=q.val:
                return False
            if p.val==q.val:
                return dfs(p.__next__,q.right) or dfs(p.__next__,q.left)
            return False
        if not root:
            return False
        if not head:
            return True
        return dfs(head,root) or self.isSubPath(head,root.right) or self.isSubPath(head,root.left)


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        def fromHeadPath(h, r):
            if not h or not r:
                return False
            if h.val != r.val:
                return False
            if not h.__next__:
                return True
            return fromHeadPath(h.__next__, r.left) or fromHeadPath(h.__next__, r.right)
        
        if not head or not root:
            return False
        if fromHeadPath(head, root):
            return True
        
        return self.isSubPath(head, root.left) or self.isSubPath(head, root.right)
    


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode, path=None, cool=None) -> bool:
        path = path or []
        cool = cool or []
        path.append(root.val)
        cool = [node.__next__ for node in cool if node.val == root.val]
        if root.val == head.val:
            cool.append(head.__next__)
            
        if None in cool:
            return True
        
        l = r = False
        if root.left:
            l = self.isSubPath(head, root.left, path.copy(), cool)
            if l is True:
                return True
        if root.right:
            r = self.isSubPath(head, root.right, path.copy(), cool)
            if r is True:
                return True

        if root.left is None and root.right is None:
            cool = []
        return False


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode, path=None, cool=None) -> bool:
        path = path or []
        cool = cool or dict()
        path.append(root.val)
        cool = {node.__next__ for node in cool if node.val == root.val}
        if root.val == head.val:
            cool.add(head.__next__)
            
        if None in cool:
            return True
        
        l = r = False
        if root.left:
            l = self.isSubPath(head, root.left, path.copy(), cool)
            if l is True:
                return True
        if root.right:
            r = self.isSubPath(head, root.right, path.copy(), cool)
            if r is True:
                return True

        if root.left is None and root.right is None:
            cool = []
        return False


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    
    def traverse(self, head: ListNode, node:ListNode, root: TreeNode) -> bool:
        if not node:
            return True
        if not root:
            return False
        print(\"comparing \" + str(root.val) + \" with \" + str(node.val))
        res = root.val == node.val
        if res:
            node = node.next
        else:
            node = head
            if root.val == node.val:
                node = node.next
        res = self.traverse(head, node, root.left)
        res = res or self.traverse(head, node, root.right)
        return res
    
    def find(self, node: ListNode, root: TreeNode) -> bool:
        if not node:
            return True
        if not root:
            return False
        print(\"comparing \" + str(root.val) + \" with \" + str(node.val))
        if node.val == root.val:
            return self.find(node.next, root.left) or self.find(node.next, root.right)
        return False
    
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        # if not root or not head:
        #     return False
        # return self.traverse(head, head, root)
        if not root:
            return False
        check = head.val == root.val
        if check and (self.find(head.next, root.left) or self.find(head.next, root.right)):
            return True
        else:
            return self.isSubPath(head, root.left) or self.isSubPath(head, root.right)

class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        if root:
            return self.traverse(root, head)
        
    def traverse(self, cur, head):
        if self.startwith(cur, head):
            return True
        else:
            if cur.left and self.traverse(cur.left, head):
                return True
            elif cur.right and self.traverse(cur.right, head):
                return True
        return False
    
    def startwith(self, startnode, head) -> bool:
        if startnode.val == head.val:
            if head.next == None:
                return True
            if startnode.left and self.startwith(startnode.left, head.next):
                return True
            elif startnode.right and self.startwith(startnode.right, head.next):
                return True
            False
        else:
            return False

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        def dfs(head, root):
            if not head: return True
            if not root: return False
            return root.val == head.val and (dfs(head.next, root.left) or dfs(head.next, root.right))
        if not head: return True
        if not root: return False
        return dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)

from math import floor
from math import ceil
from math import sqrt
from collections import deque
import numpy
from _collections import deque
#from _ast import Num # LC doesn't like this
from heapq import *
from typing import List
import random

MOD = int(1e9 + 7)
BASE = 256

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def match(head, root):
    if not head.next and root:
        return head.val == root.val
    elif not root:
        return 0
    return head.val == root.val and (match(head.next, root.left) or match(head.next, root.right))

class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        if not root:
            return 0
        return match(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right) 
        


\"\"\"
s = Solution()
n4 = TreeNode(4)
n3 = TreeNode(3, n4)
n2 = TreeNode(2, None, n3)
n4 = TreeNode(41)
n1 = TreeNode(1, n2, n4)
n5 = TreeNode(5)
n4 = TreeNode(4, None, n5)
n3 = TreeNode(3, n4)
n2 = TreeNode(2, None, n3)
n1 = TreeNode(1, None, n2)
print(s.longestZigZag(n1))
\"\"\"


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        Head = head
        @lru_cache(None)
        def helper(root,head):
            if(head is None):
                return True
            if(root is None):
                return False
            ans = False
            if(root.val == head.val):
                ans = ans or helper(root.left,head.__next__)
                ans = ans or helper(root.right, head.__next__)
            ans = ans or helper(root.left, Head)
            ans = ans or helper(root.right, Head)
            return ans
        return helper(root,head)


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        def dfs(head, root):
            if not head: return True
            if not root: return False
            if root.val == head.val:
                return dfs(head.next, root.left) or dfs(head.next, root.right)
        
        if not head: return True
        if not root: return False
        if dfs(head, root): return True
        return self.isSubPath(head, root.left) or self.isSubPath(head, root.right)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        if head is None:
            return True
        if root is None:
            return False
        return self.rfun(root,head) or self.isSubPath(head,root.left) or  self.isSubPath(head,root.right)
        
    def rfun(self,root,head):
        if head is None:
            return True
        if root is None:
            return False
        return root.val == head.val and (self.rfun(root.left,head.next) or self.rfun(root.right,head.next))

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        def dfs(head, root):
            if not head: return True
            if not root: return False
            return root.val == head.val and (dfs(head.__next__, root.left) or dfs(head.__next__, root.right))
        if not head: return True
        if not root: return False
        return dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)
        
        
#         def dfs(head, root):
#             if not head:
#                 return True

#             if not root:
#                 return False

#             if root.val == head.val:
#                 return self.isSubPath(head.next, root.left) \\
#             or self.isSubPath(head.next, root.right)
#             else:
#                 return False
        
#         if not head:
#             return True

#         if not root:
#             return False
        
#         return dfs(head,root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:        
        memo = {}
        def _isSubPath(head,listnode,root):
            if listnode is None:
                return True 
            
            if root is None:
                return False
            
            if (listnode, root) in memo:
                return memo[(listnode,root)]
            
            ret = False
            if root.val == listnode.val:
                ret = _isSubPath(head,listnode.__next__,root.left) or _isSubPath(head,listnode.__next__,root.right)
            if ret:
                memo[(listnode,root)] = ret
                return True
         
            ret = _isSubPath(head,head,root.left) or _isSubPath(head,head,root.right) 
            memo[(listnode,root)] = ret
            return ret
            
        return _isSubPath(head,head,root)
        # def dfs(head, root):
        #     if not head: return True
        #     if not root: return False
        #     return root.val == head.val and (dfs(head.next, root.left) or dfs(head.next, root.right))
        # if not head: return True
        # if not root: return False
        # return dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        def helper(temp,root):
            if not temp:
                return 1 
            if not root:
                return 0
            if root.val==temp.val:
                a=helper(temp.__next__,root.left)
                b=helper(temp.__next__,root.right)
                return a or b
            return 0 
                
        def fun(head,root):
            temp=head
            if not root :
                return 0 
            if helper(temp,root):
                return 1 
            a=fun(head,root.left)
            b=fun(head,root.right)
            return a or b
        return fun(head,root)
            


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode, path=None, cool=None) -> bool:
        path = path or []
        cool = cool or []
        path.append(root.val)
        cool_n = []
        for i in cool:
            if i.val == root.val:
                cool_n.append(i.__next__)
                if cool_n[-1] == None:
                    return True
        cool = cool_n
        if root.val == head.val:
            cool.append(head.__next__)
            if cool[-1] == None:
                return True
        
        l = r = False
        if root.left:
            l = self.isSubPath(head, root.left, path.copy(), cool)
            if l is True:
                return True
        if root.right:
            r = self.isSubPath(head, root.right, path.copy(), cool)
            if r is True:
                return True

        if root.left is None and root.right is None:
            cool = []
        return False


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:        
        memo = {}
        def _isSubPath(head,listnode,root):
            if listnode is None:
                return True 
            
            if root is None:
                return False
            
            if (listnode, root) in memo:
                return memo[(listnode,root)]
            
            ret = False
            if root.val == listnode.val:
                ret = _isSubPath(head,listnode.__next__,root.left) or _isSubPath(head,listnode.__next__,root.right)
            
            ret = ret or  _isSubPath(head,head,root.left) or _isSubPath(head,head,root.right)
            memo[(listnode,root)] = ret
            return ret 
            
        return _isSubPath(head,head,root)


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        target = \"\"
        while head:
            target = target + str(head.val)
            head = head.next
            #print(target) # LList is a str = 428

        def dfs(root, path):
            # print(path) #1426 1428
            if target in path: # matched
                return True      
            if root.left:
                ans =  dfs(root.left, path + str(root.left.val))
                if ans:  #if ans == True:
                    return True          
            if root.right:
                ans  = dfs(root.right, path + str(root.right.val))
                if ans: return True       
            return False            
        return dfs(root, str(root.val))
        
            
        

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        if head == None:
            return True
        if root == None:
            return False
        # judge root, then judge root.left and root.right
        return self.isSub(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)
    
    def isSub(self, head, node):
        # list is over
        if head == None:
            return True
        # list is not over and tree is over
        if node == None:
            return False
        # not equal
        if not head.val == node.val:
            return False
        # equal, then left and right
        return self.isSub(head.next, node.left) or self.isSub(head.next, node.right)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        s = [root]
        while s:
            t = s.pop()
            if self.dfs(head, t):
                return True
            if t:
                if t.left:
                    s.append(t.left)
                if t.right:
                    s.append(t.right)
        return False

    def dfs(self, head: ListNode, root: TreeNode) -> bool:
        # print(head.val if head else head, root.val if root else root)
        if head is None:
            return True
        if root is None:
            return False
        if root.val==head.val:
            return self.dfs(head.next, root.left) or self.dfs(head.next, root.right)
        return False

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        
        def rec(head,root,connected):
            if not head or not root:
                return False
            if connected and head.val==root.val:
                if head.__next__:
                    left=rec(head.__next__,root.left,True)
                    right=rec(head.__next__,root.right,True)
                    return left or right
                else:
                    return True
            if head.val!=root.val and connected:
                return False
            if not connected:
                if head.val==root.val:
                    left_noConn=rec(head,root.left,False)
                    right_noConn=rec(head,root.right,False)
                    if head.__next__:
                        left=rec(head.__next__,root.left,True)
                        right=rec(head.__next__,root.right,True)
                    else:
                        return True
                    return left or right or left_noConn or right_noConn
                else:
                    left_noConn=rec(head,root.left,False)
                    right_noConn=rec(head,root.right,False)
                    return left_noConn or right_noConn
                
                return left or right
        
        return rec(head,root,False)
            


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        
        visited = set()
        
        def checkNode(treePointer, listPointer):
            if listPointer == None:
                return True
            if treePointer == None and listPointer != None:
                return False
            
            if (treePointer, listPointer) in visited:
                return False
            
            if treePointer.val == listPointer.val:
                if checkNode(treePointer.left, listPointer.next) or checkNode(treePointer.right, listPointer.next):
                    return True
                
            if treePointer.val == head.val:
                if checkNode(treePointer.left, head.next) or checkNode(treePointer.right, head.next):
                    return True     
            
            if checkNode(treePointer.left, head) or checkNode(treePointer.right, head):
                    return True     
            
            visited.add((treePointer, listPointer))
            return False
        
        return checkNode(root, head)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        @lru_cache(maxsize=None)
        def helper(llNode, tNode) -> bool:
            if not llNode:
                return True
            if not tNode:
                return False
            result = False
            nonlocal head
            # print(llNode.val, tNode.val, head.val)
            if tNode.val == llNode.val:
                result = result \\
                    or helper(llNode.next, tNode.left) \\
                    or helper(llNode.next, tNode.right)
            if tNode.val == head.val:
                result = result \\
                    or helper(head.next, tNode.left) \\
                    or helper(head.next, tNode.right)
            else:
                result = result \\
                    or helper(head, tNode.left) \\
                    or helper(head, tNode.right)

            return result
        
        return helper(head, root)
        

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def dfs(self, nums, i, tree_node, memo):
        if i >= len(nums):
            return True
        if not tree_node:
            return False
        
        key = str(i) + ':' + str(id(tree_node))
        if key in memo:
            return memo[key]
        # print('i: ' + str(i) +  ', node: ' + str(id(tree_node)))
        
        if tree_node.val == nums[i]:
            left = self.dfs(nums, i+1, tree_node.left, memo)
            right = self.dfs(nums, i+1, tree_node.right, memo)
            if left or right:
                return True
            
        left = self.dfs(nums, 0, tree_node.left, memo)
        right = self.dfs(nums, 0, tree_node.right, memo)
        
        memo[key] = left or right
        
        return left or right
        
    
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        if not head:
            return True
        if not root:
            return False
        
        memo = {}
        
        nums = []
        curr = head
        while curr:
            nums.append(curr.val)
            curr = curr.next
        
        return self.dfs(nums, 0, root, memo)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        if head==None:
            return 1
        if root==None:
            return 0
        self.arr=[]
        def trav(root,val):
            if root:
                if root.val==val:
                    self.arr.append(root)
                trav(root.left,val)
                trav(root.right,val)
        trav(root,head.val)
        p=head
        while self.arr:
            p=p.next
            if p==None:
                return 1
            i=0
            r=len(self.arr)
            while i<r:
                node=self.arr.pop(0)
                if node.left:
                    if node.left.val==p.val:
                        self.arr.append(node.left)
                if node.right:
                    if node.right.val==p.val:
                        self.arr.append(node.right)
                i+=1
        return 0

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        
        def dfs(nodeL, nodeT):
            if not nodeT and nodeL:
                return False
            if not nodeL:
                return True
            if nodeL.val == nodeT.val:
                return dfs(nodeL.next, nodeT.left) or dfs(nodeL.next, nodeT.right)
            
            return False
            
            
        bfs = collections.deque([root])
        while bfs:
            node = bfs.popleft()
            if dfs(head, node):
                return True
            if node.left:
                bfs.append(node.left)
            if node.right:
                bfs.append(node.right)
        return False

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode, current=None) -> bool:
        # traverse tree checking 
        if head is None or root is None:
            return False
        if self.check_children(head, root):
            return True
        return (self.isSubPath(head, root.left) or
                self.isSubPath(head, root.right))
        
    def check_children(self, head: ListNode, root: TreeNode):
        if head is None or root is None:
            return False
        if head.val == root.val:
            if head.next is None:
                return True
            else:
                return (self.check_children(head.next, root.left) or
                        self.check_children(head.next, root.right))

        else:
            return False

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        def checker(l1, l2):
            if len(l1) < len(l2): return False
            
            for i in range(len(l2)):
                if l2[len(l2)-1-i] != l1[len(l1)-1-i]: return False
            return True
        
        pattern = []
        while(head):
            pattern.append(head.val)
            head = head.next
        
        self.res = False
        def traverse(root, S=[]):
            if self.res: return True
            if root == None: return False
            if checker(S+[root.val], pattern): 
                self.res = True
                return True
            traverse(root.left, S+[root.val])
            traverse(root.right, S+[root.val])
        
        traverse(root)
        return self.res

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        # 6:39 10/7/20
        
        # BFS + DFS
        
        def dfs(node):
            if not node:
                return
            if node.val == head.val:
                q.appendleft((node, head, set()))
            dfs(node.left)
            dfs(node.right)
        
        # Step 1: Use DFS to add every node that has the same value with that of head to a queue
        q = collections.deque()
        dfs(root)
        
        # Step 2: Use BFS to walk down the path where both node and linked list have the same value
        while q:
            tree_node, list_node, visited = q.pop()
            if tree_node.val == list_node.val:
                if not list_node.__next__:  
                    return True # Finally, we reached the end of linked list. 
                for nei in (tree_node.left, tree_node.right):
                    if nei and nei not in visited and nei.val == list_node.next.val:
                        visited.add(nei)
                        q.appendleft((nei, list_node.__next__, visited))
                        visited.remove(nei)
        return False
        

            
           
                    


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        if (not root and not head) or (not root and head):
            return False
        elif root and not head:
            return True
        
        memory = []
        
        def preorder(node: ListNode):
            if not node:
                return
            
            nonlocal head
            nonlocal memory
            
            if node.val == head.val:
                memory.append(node)
            
            preorder(node.left)
            preorder(node.right)
            
        preorder(root)
        head = head.__next__
        
        while head and memory:
            newMemory = []
            
            for node in memory:
                if node.left and node.left.val == head.val:
                    newMemory.append(node.left)
                if node.right and node.right.val == head.val:
                    newMemory.append(node.right)
            
            head = head.__next__
            memory = newMemory
                    
        return len(memory) > 0


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        paths = []
        def dfs(root, arr):
            arr1 = arr + [str(root.val)]
            if root.left:
                dfs(root.left, arr1)
            if root.right:
                dfs(root.right, arr1)
            if not root.left and not root.right:
                paths.append(arr1)
        dfs(root, [])
        target = []
        while head:
            target.append(str(head.val))
            head = head.next
        tar = '#'.join(target)
        for path in paths:
            if tar in '#'.join(path):
                return True
        return False

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPathHelper(self, cur, root):
        if not cur:
            return True
        if not root:
            return False
        return cur.val == root.val and (self.isSubPathHelper(cur.__next__, root.left) or self.isSubPathHelper(cur.__next__, root.right))  
        
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        if not root:
            return False
        found = self.isSubPathHelper(head, root)
        nodes = []
        if root.left:
            nodes.append(root.left)
        if root.right:
            nodes.append(root.right)
        for node in nodes:
            found |= self.isSubPath(head, node)
        return found         
            


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    # Time Complextity O(root)*O(head)
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        helper = set()
        
        # Find all possible start
        def getStart(p):
            if p:
                if p.val == head.val:
                    helper.add(p)
                getStart(p.left)
                getStart(p.right)
                
        # Main
        getStart(root)
        #print(helper)
        
        while head.next:
            new = set()
            for node in helper:
                if node.val == head.val:
                    if node.left:
                        new.add(node.left)
                    if node.right:
                        new.add(node.right)
            helper = new
            
            if not helper:
                return False
            
            head = head.next

        return (head.val in [node.val for node in helper])

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def _iter(self, root):
        if root is not None:
            yield root
            yield from self._iter(root.left)
            yield from self._iter(root.right)
    
    def _search(self, head, root):
        if head is None or root is None:
            return head is None
        elif head.val == root.val:
            return self._search(head.next, root.left) or self._search(head.next, root.right)
        else:
            return False
        
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        for node in self._iter(root):
            if node.val == head.val:
                if self._search(head, node):
                    return True
        return False

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        if not head or not root:
            return False
        queue = deque([root])
        while queue:
            tNode = queue.pop()
            if tNode.val == head.val:
                if self.getListExistsAsPath(head,tNode):
                    return True
            if tNode.left:
                queue.appendleft(tNode.left)
            if tNode.right:
                queue.appendleft(tNode.right)
        return False
    
    def getListExistsAsPath(self,lNode,tNode):
        if not lNode:
            return True
        if not tNode or tNode.val != lNode.val:
            return False
        
        return True and (self.getListExistsAsPath(lNode.__next__,tNode.left) or self.getListExistsAsPath(lNode.__next__,tNode.right))
            
           
                    


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        if not head:
            return True
        if not root:
            return False
        return self.dfs(head,root) or self.isSubPath(head,root.left) or self.isSubPath(head,root.right) 
        
    def dfs(self,head,root):
        if not head:
            return True
        if not root:
            return False
        return head.val==root.val and (self.dfs(head.next,root.left) or self.dfs(head.next,root.right))

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        def dfs(cur, node):
            if not cur:
                return True
            if not node:
                return False
            if cur.val == node.val:
                return dfs(cur.__next__, node.left) or dfs(cur.__next__, node.right)
            return False
        stack = [root]
        while stack:
            for node in stack:
                cur = head
                if dfs(cur, node):
                    return True
            stack = [leaf for node in stack for leaf in [node.left, node.right] if leaf]
        return False


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    
    def matchPath(self, head, root):
        if head is None:
            return True
        if root is None:
            return False
        
        if head.val != root.val:
            return False
        
        if self.matchPath(head.next, root.left):
            return True
        
        if self.matchPath(head.next, root.right):
            return True
        
        return False
        
    
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        nexts = [root]
        while len(nexts) > 0:
            node = nexts.pop()
            if node.val == head.val:
                if self.matchPath(head, node):
                    return True
            if node.left:
                nexts.append(node.left)
            if node.right:
                nexts.append(node.right)
        
        return False

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        result = False
        if not root:
            return False
        
        result = self.isSubPath(head, root.left) or self.isSubPath(head, root.right)
        
        if head.val == root.val:
            l_node = head
            g_node = root
            result = result or self.match(head, root)
        
        return result
            
    def match(self, head: ListNode, root: TreeNode) -> bool:
        if not head:
            return True
        
        if not root or head.val != root.val:
            return False
        
        return self.match(head.next, root.left) or self.match(head.next, root.right)