两棵二叉搜索树中的所有元素

题目描述：

给你 root1 和 root2 这两棵二叉搜索树。请你返回一个列表，其中包含 两棵树 中的所有整数并按 升序 排序。.

示例 1：

输入：root1 = [2,1,4], root2 = [1,0,3]
输出：[0,1,1,2,3,4]
示例 2：

输入：root1 = [1,null,8], root2 = [8,1]
输出：[1,1,8,8]

提示：

每棵树的节点数在 [0, 5000] 范围内
-105 <= Node.val <= 105

思路:

时间复杂度：O(m+n),空间复杂度O(m+n)

中序遍历，然后有个有序数组合并

代码:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func getAllElements(root1 *TreeNode, root2 *TreeNode) []int {
    var res,res1,res2 []int
    var dfs func(root *TreeNode)
    dfs = func(root *TreeNode){
        if root == nil{
            return 
        }
        dfs(root.Left)
        res2 = append(res2, root.Val)
        dfs(root.Right)
    }
    dfs(root1)
    res1 = res2
    res2 = []int{}
    dfs(root2)
    l,r ,m,n := 0,0,len(res1),len(res2)
    for l<m && r <n{
        if res1[l]<res2[r]{
           
            res = append(res, res1[l])
             l++
        }else{
            res = append(res, res2[r])
             r++
        }
    }
    for ;l<m;l++{
        res = append(res, res1[l])
    }
    for ;r<n;r++{
        res = append(res, res2[r])
    }
    return res
}

代码效率：

执行用时：80 ms, 在所有 Go 提交中击败了86.21%的用户
内存消耗：8 MB, 在所有 Go 提交中击败了63.79%的用户