[Leetcode/Tree, Binary Search Tree, DFS] 1305. 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:
    def getAllElements(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> List[int]:
        def helper(root):
            if not root:
                return []

            return helper(root.left) + [root.val] + helper(root.right)

        one = helper(root1) # [1, 4, 2]
        two = helper(root2) # [0, 1, 3]
        return sorted(one+two)

# 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: Optional[TreeNode], root2: Optional[TreeNode]) -> List[int]:
        # binary search tree -> left < right (two-pointers)
        def helper(root):
            if not root:
                return []

            return helper(root.left) + [root.val] + helper(root.right)

        one = helper(root1) # [1, 4, 2]
        two = helper(root2) # [0, 1, 3]
        
        res = []
        i, j = 0,0

        while i < len(one) and j <len(two):
            if one[i] <= two[j]:
                res.append(one[i])
                i += 1
            else:
                res.append(two[j])
                j += 1

        if i < len(one):
            return res + one[i:len(one)+1]
        if j < len(two):
            return res + two[j:len(two)+1]