Description
Given a linked list head and a binary tree root, return true if starting from some node in the tree there is a downward path matching the list.
Examples
Input:
head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]Output:
trueExplanation:
Starting from a node with value 4 in the tree, there exists a downward path through nodes 4 -> 2 -> 8 that matches the linked list sequence exactly. The algorithm checks each tree node as a potential starting point and verifies if the linked list can be traced through consecutive parent-to-child connections.
Input:
head = [1], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]Output:
trueExplanation:
Edge case with a single-element array.
Input:
head = [2,6], root = [1,2,3,null,6,4,5]Output:
trueExplanation:
The linked list [2,6] can be found as a downward path in the tree starting from the left child of root (value 2) and continuing to its left child (value 6).
Constraints
- •
1 ≤ list nodes, tree nodes ≤ 2500