给你
root1
和root2
这两棵二叉搜索树。请你返回一个列表,其中包含 两棵树 中的所有整数并按 升序 排序。.
对俩树进行中序遍历,遍历后得到的是俩有序的数组,再对这俩数组根据大小,合并到一个新的数组,即可。
func getAllElements(root1 *TreeNode, root2 *TreeNode) []int {
ans := make([]int, 0)
ldrRes1 := make([]int, 0)
ldrRes2 := make([]int, 0)
ldr(root1, &ldrRes1)
ldr(root2, &ldrRes2)
ans = sortNums(ldrRes1,ldrRes2)
//ans = append(append(ans,ldrRes1...),ldrRes2...)
//sort.Ints(ans)
return ans
}
// 中序遍历
func ldr(root *TreeNode, ldrRes *[]int) {
if root == nil {
return
} else {
ldr(root.Left, ldrRes)
*ldrRes = append(*ldrRes, root.Val)
ldr(root.Right, ldrRes)
}
}
func sortNums(nums1, nums2 []int) []int {
// num1,和num2 是中序遍历,对于二叉搜索树,中序遍历就是升序
ans := make([]int, 0)
m, n := len(nums1), len(nums2)
// 俩指针
i, j := 0, 0
for {
// 有一个走完,就跳出循环
if i >= m || j >= n {
break
}
if nums1[i] >= nums2[j] {
ans = append(ans, nums2[j])
j++
} else if nums1[i] < nums2[j] {
ans = append(ans, nums1[i])
i++
}
}
// 哪个没有走完 ,就把剩下的都追加到ans中即可
if i != m {
ans = append(ans, nums1[i:]...)
}
if j != n {
ans = append(ans, nums2[j:]...)
}
return ans
}