Linked List in Binary Tree

Given a linked list head and a binary tree root, determine whether the list's values occur along a downward path in the tree in the same order.

The path may start at any tree node. Each next list value must match an immediate left or right child of the previous tree node; you cannot skip levels or move upward. The path need not end at a leaf. Return true if such a path exists, otherwise return false.

The examples represent the linked list as an array and the tree in level order, with null for missing children.

Example 1:

Input: head = [2,4]
root = [1,2,3,4]

Output: true

Explanation: The path starts at node 2, below the root, and follows its left child 4. These consecutive values match the entire list.

Example 2:

Input: head = [1,4]
root = [1,2,3,4]

Output: false

Explanation: Reaching 4 from root 1 requires passing through node 2. Skipping that node is not allowed, and no other node with value 1 starts a matching path.

Example 3:

Input: head = [1,2]
root = [1,2,3,4]

Output: true

Explanation: The root 1 and its left child 2 match the list. Node 2 also has child 4, but a matching path does not need to end at a leaf.

Constraints:

• The tree contains between 1 and 2500 nodes.
• The linked list contains between 1 and 100 nodes.
• All values in the tree and linked list are between 1 and 100.