## 1367. Linked List in Binary Tree

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.

Example 1:

```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.
```

Example 2:

```Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
```

Example 3:

```Input: head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: false
Explanation: There is no path in the binary tree that contains all the elements of the linked list from `head`.
```

Constraints:

• The number of nodes in the tree will be in the range `[1, 2500]`.
• The number of nodes in the list will be in the range `[1, 100]`.
• `1 <= Node.val <= 100` for each node in the linked list and binary tree.

## Rust Solution

``````struct Solution;
use rustgym_util::*;

trait Preorder {
fn preorder(&self, cur: &mut Vec<i32>, found: &mut bool, path: &[i32]);
}

fn preorder(&self, cur: &mut Vec<i32>, found: &mut bool, path: &[i32]) {
if let Some(node) = self {
let node = node.borrow();
cur.push(node.val);
if cur.ends_with(path) {
*found = true;
}
node.left.preorder(cur, found, path);
node.right.preorder(cur, found, path);
cur.pop();
}
}
}

impl Solution {
let mut path = vec![];
while let Some(node) = head {
path.push(node.val);
}
let mut cur = vec![];
let mut res = false;
root.preorder(&mut cur, &mut res, &path);
res
}
}

#[test]
fn test() {
let head = list!(4, 2, 8);
let root = tree!(
1,
tree!(4, None, tree!(2, tree!(1), None)),
tree!(4, tree!(2, tree!(6), tree!(8, tree!(1), tree!(3))), None)
);
let res = true;