943. Linked List in Binary Tree

Given the values of a linked list and the root of a binary tree, determine whether the linked list corresponds to some downward path in the tree — a connected sequence of nodes from some starting node following parent-to-child edges, matching the list values in order. Return true or false. The input gives the list as a JSON array and the tree as a level-order array, separated by ' | '.

Input: A JSON list array and a level-order tree array, separated by ' | '.

Output: Boolean — true or false.

Examples

Input: [4,2,8] | [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
Explanation: The list matches a downward path.

Input: [1,4,2,6] | [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
Explanation: Another matching path.

Input: [1,10] | [1,2,3]
Output: false
Explanation: No matching path.

Constraints

• 1<=list<=100
• 1<=nodes<=2500
• values 1..100

Asked by