1305. All Elements in Two Binary Search Trees

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 5000 nodes.
  • Each node's value is between [-10^5, 10^5].

Rust Solution

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);
}

Having problems with this solution? Click here to submit an issue on github.