1367.md

1367. Linked List in Binary Tree

Level:

Topic:

Question

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.

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.

Intuition

Recursive: (DFS)

1. Solve only compare the root and head

   • stop comparing when the linked list reaches the end
   • or the tree has ended but linked list is not
   • if the values are different, stop
   • otherwise, continue to search (either the left child or right)

2. Since the head is not always the root

   • compare along tree traversal of every node

Code

Time: O(n * min(l,h)))
Space: O(h) where n = tree size, h = tree height, l = list length

Recursive

public boolean isSubPath(ListNode head, TreeNode root) {
    if (root == null)
        return false;

    // traversal
    return isSame(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
}


private boolean isSame(ListNode head, TreeNode root) {
    if (head == null)
        return true;
    if (root == null)
        return false;

    // the curernt subpath is ended
    if (head.val != root.val)
        return false;

    // if they are the same value, continue to search its subpath
    return isSame(head.next, root.left) || isSame(head.next, root.right);
}