LC 1305 [M] All Elements in Two Binary Search Trees - ALawliet/algorithms GitHub Wiki

# 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:
    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
        inorder1 = []
        inorder2 = []
        
        def inorder(node, res):
            if not node: return
            inorder(node.left, res)
            res.append(node.val)
            inorder(node.right, res)
            
        inorder(root1, inorder1)
        inorder(root2, inorder2)
                
        def merge2sorted(A, B):
            res = []
            m = 0
            n = 0
            while m < len(A) and n < len(B):
                if A[m] < B[n]:
                    res.append(A[m])
                    m += 1
                else:
                    res.append(B[n])
                    n += 1
            res = res + A[m:] + B[n:]
            return res
                    
        return merge2sorted(inorder1, inorder2)