[Leetcode] Problem 1305 - All Elements in Two Binary Search Trees

Posted on | In ,

Given two binary search trees root1 and root2.

Return a list containing all the integers from both trees sorted in ascending order.

Example

No.1

00Y3WD.png

Input: root1 = [2,1,4], root2 = [1,0,3]

Output: [0,1,1,2,3,4]

No.2

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2]

Output: [-10,0,0,1,2,5,7,10]

No.3

Input: root1 = [], root2 = [5,1,7,0,2]

Output: [0,1,2,5,7]

No.4

Input: root1 = [0,-10,10], root2 = []

Output: [-10,0,10]

No.5

00YDfS.png

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
    List<Integer> result = new ArrayList<>();
    Queue<Integer> list1 = new LinkedList<>();
    Queue<Integer> list2 = new LinkedList<>();

    inorder(list1, root1);
    inorder(list2, root2);

    while (!list1.isEmpty() || !list2.isEmpty()) {
        if (list1.isEmpty())
            result.add(list2.poll());
        else if (list2.isEmpty())
            result.add(list1.poll());
        else
            result.add(list1.peek() < list2.peek() ? list1.poll() : list2.poll());
    }

    return result;
}

private void inorder(Queue<Integer> list, TreeNode root) {
    if (root == null)
        return;

    inorder(list, root.left);
    list.add(root.val);
    inorder(list, root.right);
}