1305. All Elements in Two Binary Search Trees

Medium

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

• -10^5 <= Node.val <= 10^5

解題

Runtime: 96 ms, faster than 92.31%

Memory Usage: 8.3 MB, less than 65.38%

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func getAllElements(root1 *TreeNode, root2 *TreeNode) []int {
    arr1 := make([]int, 0)
    arr2 := make([]int, 0)

    var helper func(*TreeNode, *[]int)
    helper = func(root *TreeNode, arr *[]int) {
        if root == nil {
            return
        }

        helper(root.Left, arr)
        *arr = append(*arr, root.Val)
        helper(root.Right, arr)
    }

    helper(root1, &arr1)
    helper(root2, &arr2)

    ans := make([]int, 0)
    i1, i2 := 0, 0 
    for i1 < len(arr1) && i2 < len(arr2) {
        if arr1[i1] < arr2[i2] {
            ans = append(ans, arr1[i1])
            i1++
        } else {
            ans = append(ans, arr2[i2])
            i2++
        }
    }

    if i1 < len(arr1) {
        ans = append(ans, arr1[i1:]...)
    }

    if i2 < len(arr2) {
        ans = append(ans, arr2[i2:]...)
    }

    return ans
}