1305. All Elements in Two Binary Search Trees

Description

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 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]

Constraints:

• The number of nodes in each tree is in the range [0, 5000].
• 105 <= Node.val <= 105

---

Solutions

Solution 1

Intuition

1. inOrder travel each tree, and put their values into a list
2. sort this list

Code

List < Integer > res = new ArrayList < > ();
public List < Integer > getAllElements(TreeNode root1, TreeNode root2) {

    inOrder(root1);
    inOrder(root2);
    Collections.sort(res);
    return res;
}

private void inOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    inOrder(root.left);
    res.add(root.val);
    inOrder(root.right);
}

Complexity

• Time: O(nlogn)
• Space: O(n)

---

Solution 2

Intuition

1. use two stacks to travel trees inorder
2. pop smaller node firstly

Code

public List < Integer > getAllElements(TreeNode root1, TreeNode root2) {
    List < Integer > res = new ArrayList < > ();
    Stack < TreeNode > stack1 = new Stack < > (), stack2 = new Stack < > ();

    while (root1 != null || !stack1.isEmpty() || root2 != null || !stack2.isEmpty()) {
        while (root1 != null) {
            stack1.push(root1);
            root1 = root1.left;
        }
        while (root2 != null) {
            stack2.push(root2);
            root2 = root2.left;
        }
        if (stack2.isEmpty() || (!stack1.isEmpty() && stack1.peek().val < stack2.peek().val)) {
            root1 = stack1.pop();
            res.add(root1.val);
            root1 = root1.right;
        } else {
            root2 = stack2.pop();
            res.add(root2.val);
            root2 = root2.right;
        }
    }

    return res;
}

Complexity

• Time: O(n)
• Space: O(n)

---

Solution 3

Intuition

1. inorder travel each trees, and store there values in different lists
2. merge sort these two lists

Code

public List < Integer > getAllElements(TreeNode root1, TreeNode root2) {
  ArrayList < Integer > res = new ArrayList < > (), list1 = new ArrayList < > (), list2 = new ArrayList < > ();
  inOrder(root1, list1);
  inOrder(root2, list2);

  int i = 0, j = 0;
  while (i < list1.size() && j < list2.size()) {
    if (list1.get(i) < list2.get(j)) {
      res.add(list1.get(i++));
    } else {
      res.add(list2.get(j++));
    }
  }

  while (i < list1.size()) {
    res.add(list1.get(i++));
  }
  while (j < list2.size()) {
    res.add(list2.get(j++));
  }

  return res;
}

private void inOrder(TreeNode root, ArrayList < Integer > list) {
  if (root == null) {
    return;
  }
  inOrder(root.left, list);
  list.add(root.val);
  inOrder(root.right, list);
}

Complexity

• time: O(n)
• size: O(n)

Similar Questions