1305. All Elements in Two Binary Search Trees

1305. All Elements in Two Binary Search Trees (Medium)

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

Related Topics:
Sort, Tree

Solution 1.

// OJ: https://leetcode.com/problems/all-elements-in-two-binary-search-trees/
// Author: github.com/lzl124631x
// Time: O(A + B)
// Space: O(HA + HB)
class BstIterator{
    stack<TreeNode*> s;
    void add(TreeNode *root) {
        while (root) {
            s.push(root);
            root = root->left;
        }
    }
public:
    BstIterator(TreeNode *root) {
        add(root);
    }
    bool hasNext() {
        return s.size();
    }
    int peek() {
        return s.top()->val;
    }
    void next() {
        auto root = s.top();
        s.pop();
        add(root->right);
    }
};
class Solution {
public:
    vector<int> getAllElements(TreeNode* a, TreeNode* b) {
        vector<int> ans;
        BstIterator i(a), j(b);
        while (i.hasNext() && j.hasNext()) {
            int x = i.peek(), y = j.peek();
            if (x <= y) {
                ans.push_back(x);
                i.next();
            }
            if (y <= x) {
                ans.push_back(y);
                j.next();
            }
        }
        if (j.hasNext()) swap(i, j);
        while (i.hasNext()) {
            ans.push_back(i.peek());
            i.next();
        }
        return ans;
    }
};