Linked List in Binary Tree

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


Intuition

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.

Solution


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 = head.next
            head.next = prev
            prev = head
            head = tmp
        return prev

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

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

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