Linked List in Binary Tree

Problem Id: 1367 Difficulty: Medium Tag: Linked List Tag: Dynamic Programming Tag: Tree


We could mark the path during DFS. When a node is equal to the value of the last node in the linked list, we could search up to see if it could match the requirement.

The worst time complexity is O(n * m) where n is the number of nodes in the tree and m is the number of nodes in the linked list.


class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        path = []
        reverse = self._reverse(head)
        return self._dfs(root, reverse, path)

    def _reverse(self, head):
        prev = None
        while head:
            tmp =
   = prev
            prev = head
            head = tmp
        return prev

    def _dfs(self, node, reverse, path):
        if node is None:
            return False

        tmp = reverse
        i = len(path) - 1
        while i >= 0 and tmp and tmp.val == path[i]:
            i -= 1
            tmp =
        if tmp is None:
            return True

        if self._dfs(node.left, reverse, path):
            return True
        if self._dfs(node.right, reverse, path):
            return True
        return False