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
Solution:
/**
* Definition for a binary tree node.
* 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;
* }
* }
*/
class Solution {
public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
Stack<TreeNode> s1 = new Stack<>();
Stack<TreeNode> s2 = new Stack<>();
List<Integer> result = new ArrayList<>();
while(root1!=null || root2!=null || !s1.empty() || !s2.empty()){
while(root1!=null)
{
s1.push(root1);
root1=root1.left;
}
while(root2!=null)
{
s2.push(root2);
root2=root2.left;
}
if(s2.empty() || (!s1.empty() && s1.peek().val <= s2.peek().val))
{
root1 = s1.pop();
result.add(root1.val);
root1 = root1.right;
}
else
{
root2 = s2.pop();
result.add(root2.val);
root2 = root2.right;
}
}
return result;
}
}