Given two binary search trees root1 and root2.
Return a list containing all the integers from both trees sorted in ascending order.
Example 1:
Input: root1 = [2,1,4], root2 = [1,0,3] Output: [0,1,1,2,3,4]
Example 2:
Input: root1 = [0,-10,10], root2 = [5,1,7,0,2] Output: [-10,0,0,1,2,5,7,10]
Example 3:
Input: root1 = [], root2 = [5,1,7,0,2] Output: [0,1,2,5,7]
Example 4:
Input: root1 = [0,-10,10], root2 = [] Output: [-10,0,10]
Example 5:
Input: root1 = [1,null,8], root2 = [8,1] Output: [1,1,8,8]
Constraints:
- Each tree has at most
5000nodes. - Each node's value is between
[-10^5, 10^5].
struct Solution;
use rustgym_util::*;
trait Inorder {
fn inorder(&self, v: &mut Vec<i32>);
}
impl Inorder for TreeLink {
fn inorder(&self, v: &mut Vec<i32>) {
if let Some(node) = self {
let val = node.borrow().val;
let left = &node.borrow().left;
let right = &node.borrow().right;
left.inorder(v);
v.push(val);
right.inorder(v);
}
}
}
impl Solution {
fn get_all_elements(root1: TreeLink, root2: TreeLink) -> Vec<i32> {
let mut res = vec![];
let mut v1 = vec![];
let mut v2 = vec![];
root1.inorder(&mut v1);
root2.inorder(&mut v2);
let mut i = 0;
let mut j = 0;
let n = v1.len();
let m = v2.len();
while i < n || j < m {
if i == n {
res.push(v2[j]);
j += 1;
continue;
}
if j == m {
res.push(v1[i]);
i += 1;
continue;
}
if v1[i] < v2[j] {
res.push(v1[i]);
i += 1;
} else {
res.push(v2[j]);
j += 1;
}
}
res
}
}
#[test]
fn test() {
let root1 = tree!(2, tree!(1), tree!(4));
let root2 = tree!(1, tree!(0), tree!(3));
let res = vec![0, 1, 1, 2, 3, 4];
assert_eq!(Solution::get_all_elements(root1, root2), res);
let root1 = tree!(0, tree!(-10), tree!(10));
let root2 = tree!(5, tree!(1, tree!(0), tree!(2)), tree!(7));
let res = vec![-10, 0, 0, 1, 2, 5, 7, 10];
assert_eq!(Solution::get_all_elements(root1, root2), res);
let root1 = None;
let root2 = tree!(5, tree!(1, tree!(0), tree!(2)), tree!(7));
let res = vec![0, 1, 2, 5, 7];
assert_eq!(Solution::get_all_elements(root1, root2), res);
let root1 = tree!(0, tree!(-10), tree!(10));
let root2 = None;
let res = vec![-10, 0, 10];
assert_eq!(Solution::get_all_elements(root1, root2), res);
}