Formatted question description: https://leetcode.ca/all/1305.html

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

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> elements1 = inorderTraversal(root1);
        List<Integer> elements2 = inorderTraversal(root2);
        List<Integer> allElements = new ArrayList<Integer>();
        int size1 = elements1.size(), size2 = elements2.size();
        int index1 = 0, index2 = 0;
        while (index1 < size1 && index2 < size2) {
            int element1 = elements1.get(index1), element2 = elements2.get(index2);
            if (element1 <= element2) {
                allElements.add(element1);
                index1++;
            } else {
                allElements.add(element2);
                index2++;
            }
        }
        while (index1 < size1) {
            int element1 = elements1.get(index1);
            allElements.add(element1);
            index1++;
        }
        while (index2 < size2) {
            int element2 = elements2.get(index2);
            allElements.add(element2);
            index2++;
        }
        return allElements;
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> inorderTraversal = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            TreeNode visitNode = stack.pop();
            inorderTraversal.add(visitNode.val);
            node = visitNode.right;
        }
        return inorderTraversal;
    }
}

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

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def getAllElements(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: List[int]
        """
        nums1 = []
        nums2 = []
        self.inOrder(root1, nums1)
        self.inOrder(root2, nums2)
        return self.merge(nums1, nums2)
        
        
    def inOrder(self, root, nums):
        if not root:
            return
        self.inOrder(root.left, nums)
        nums.append(root.val)
        self.inOrder(root.right, nums)
    
    def merge(self, nums1, nums2):
        res = []
        p1 = 0
        p2 = 0
        while p1 < len(nums1) and p2 < len(nums2):
            if nums1[p1] < nums2[p2]:
                res.append(nums1[p1])
                p1 += 1
            else:
                res.append(nums2[p2])
                p2 += 1
        if p1 < len(nums1):
            res.extend(nums1[p1:])
        if p2 < len(nums2):
            res.extend(nums2[p2:])
        return res

1305 - All Elements in Two Binary Search Trees

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

Solution 1.

All Problems

All Solutions