rustgym/leetcode/
_1367_linked_list_in_binary_tree.rs

1struct Solution;
2use rustgym_util::*;
3
4trait Preorder {
5    fn preorder(&self, cur: &mut Vec<i32>, found: &mut bool, path: &[i32]);
6}
7
8impl Preorder for TreeLink {
9    fn preorder(&self, cur: &mut Vec<i32>, found: &mut bool, path: &[i32]) {
10        if let Some(node) = self {
11            let node = node.borrow();
12            cur.push(node.val);
13            if cur.ends_with(path) {
14                *found = true;
15            }
16            node.left.preorder(cur, found, path);
17            node.right.preorder(cur, found, path);
18            cur.pop();
19        }
20    }
21}
22
23impl Solution {
24    fn is_sub_path(mut head: ListLink, root: TreeLink) -> bool {
25        let mut path = vec![];
26        while let Some(node) = head {
27            path.push(node.val);
28            head = node.next;
29        }
30        let mut cur = vec![];
31        let mut res = false;
32        root.preorder(&mut cur, &mut res, &path);
33        res
34    }
35}
36
37#[test]
38fn test() {
39    let head = list!(4, 2, 8);
40    let root = tree!(
41        1,
42        tree!(4, None, tree!(2, tree!(1), None)),
43        tree!(4, tree!(2, tree!(6), tree!(8, tree!(1), tree!(3))), None)
44    );
45    let res = true;
46    assert_eq!(Solution::is_sub_path(head, root), res);
47}