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

Two-Way Recursive DFS Solutions

/**
 * 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 void inorder(TreeNode root, LinkedList<Integer> l1){
        if(root==null){
            return;
        }inorder(root.left,l1);
        l1.add(root.val);
        inorder(root.right,l1);
    }
    public void inorder2(TreeNode root,LinkedList<Integer> l1,LinkedList<Integer> l2){
        if(root==null){
            return;
        }inorder2(root.left,l1,l2);
        while(!l1.isEmpty() && root.val> l1.peek()){
            l2.add(l1.poll());
        }l2.add(root.val);
        inorder2(root.right,l1,l2);
    }
    
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        LinkedList<Integer> l1=new LinkedList<Integer>();
        inorder(root1,l1);
        LinkedList<Integer> l2=new LinkedList<>();
        inorder2(root2,l1,l2);
        l2.addAll(l1);
        return l2;
    }
}

Leave a reply