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
}