LC1305 All Elements in Two Binary Search Trees

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    # time O(N) space O(N)
    """
        main idea: use inorder traversal to get all value from each node in both trees. use feature of queue to append each node and popleft min val node at O(1)
    """
    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
        q1, q2 = collections.deque(), collections.deque()
        res = []
        def inorder(node,q):
            if not node:
                return 
            inorder(node.left,q)
            q.append(node.val)
            inorder(node.right,q)
            
        inorder(root1,q1)
        inorder(root2,q2)
        while q1 or q2:
            if not q1:
                res.append(q2.popleft())
            elif not q2:
                res.append(q1.popleft())
            else:
                res.append(q1.popleft()if q1[0]< q2[0] else q2.popleft())
        return res