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.

Source: leetcode | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Graph traversal

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) + '-'
		st = [(r0, '-')]
		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


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)


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)


class Solution:

	def isSubPath(self, head: ListNode, root: TreeNode) -> bool:

		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)


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)


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


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
		elif 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


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)


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))


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)


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)


class Solution:

	def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
		if head == None:
			return True
		if root == None:
			return False
		return self.isSub(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)

	def isSub(self, head, node):
		if head == None:
			return True
		if node == None:
			return False
		if not head.val == node.val:
			return False
		return self.isSub(head.next, node.left) or self.isSub(head.next, node.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:
		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


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)


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)


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]
		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)


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


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


class Solution:

	def isSubPath(self, head: ListNode, root: TreeNode, current=None) -> bool:
		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


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


class Solution:

	def isSubPath(self, head: ListNode, root: TreeNode) -> bool:

		def dfs(node):
			if not node:
				return
			if node.val == head.val:
				q.appendleft((node, head, set()))
			dfs(node.left)
			dfs(node.right)
		q = collections.deque()
		dfs(root)
		while q:
			(tree_node, list_node, visited) = q.pop()
			if tree_node.val == list_node.val:
				if not list_node.__next__:
					return True
				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


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


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


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


class Solution:

	def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
		helper = set()

		def getStart(p):
			if p:
				if p.val == head.val:
					helper.add(p)
				getStart(p.left)
				getStart(p.right)
		getStart(root)
		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]


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


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))


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


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


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)