rustgym/leetcode/
_1305_all_elements_in_two_binary_search_tree.rs

1struct Solution;
2use rustgym_util::*;
3
4trait Inorder {
5    fn inorder(&self, v: &mut Vec<i32>);
6}
7
8impl Inorder for TreeLink {
9    fn inorder(&self, v: &mut Vec<i32>) {
10        if let Some(node) = self {
11            let val = node.borrow().val;
12            let left = &node.borrow().left;
13            let right = &node.borrow().right;
14            left.inorder(v);
15            v.push(val);
16            right.inorder(v);
17        }
18    }
19}
20
21impl Solution {
22    fn get_all_elements(root1: TreeLink, root2: TreeLink) -> Vec<i32> {
23        let mut res = vec![];
24        let mut v1 = vec![];
25        let mut v2 = vec![];
26        root1.inorder(&mut v1);
27        root2.inorder(&mut v2);
28        let mut i = 0;
29        let mut j = 0;
30        let n = v1.len();
31        let m = v2.len();
32        while i < n || j < m {
33            if i == n {
34                res.push(v2[j]);
35                j += 1;
36                continue;
37            }
38            if j == m {
39                res.push(v1[i]);
40                i += 1;
41                continue;
42            }
43            if v1[i] < v2[j] {
44                res.push(v1[i]);
45                i += 1;
46            } else {
47                res.push(v2[j]);
48                j += 1;
49            }
50        }
51        res
52    }
53}
54
55#[test]
56fn test() {
57    let root1 = tree!(2, tree!(1), tree!(4));
58    let root2 = tree!(1, tree!(0), tree!(3));
59    let res = vec![0, 1, 1, 2, 3, 4];
60    assert_eq!(Solution::get_all_elements(root1, root2), res);
61    let root1 = tree!(0, tree!(-10), tree!(10));
62    let root2 = tree!(5, tree!(1, tree!(0), tree!(2)), tree!(7));
63    let res = vec![-10, 0, 0, 1, 2, 5, 7, 10];
64    assert_eq!(Solution::get_all_elements(root1, root2), res);
65    let root1 = None;
66    let root2 = tree!(5, tree!(1, tree!(0), tree!(2)), tree!(7));
67    let res = vec![0, 1, 2, 5, 7];
68    assert_eq!(Solution::get_all_elements(root1, root2), res);
69    let root1 = tree!(0, tree!(-10), tree!(10));
70    let root2 = None;
71    let res = vec![-10, 0, 10];
72    assert_eq!(Solution::get_all_elements(root1, root2), res);
73}
rustgym/leetcode/_1305_all_elements_in_two_binary_search_tree.rs

rustgym/leetcode/
_1305_all_elements_in_two_binary_search_tree.rs
