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