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

题目#

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

示例 1：

img

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

示例 2：

img

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

提示：

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

思路#

一眼直接遍历再sort快排，这样主要是快排的O（nlgn）

优化：要利用上搜索树的特性，中序遍历是有序的，可以得到两个有序数组，这样再用双指针就可以得到O（m+n）的时间复杂度。

代码#

一般：

func getAllElements(root1 *TreeNode, root2 *TreeNode) []int {
	// 最简单，收集再排序，Onlgn
	var nums []int
	nums = append(nums, preOrder(root1)...)
	nums = append(nums, preOrder(root2)...)
	sort.Ints(nums)
	return nums
}

func preOrder(root *TreeNode) (nums []int) {
	var traverse func(*TreeNode)
	traverse = func(root *TreeNode) {
		if root == nil {
			return
		}
		nums = append(nums, root.Val)
		traverse(root.Left)
		traverse(root.Right)
	}

	return
}
  • 48/48 cases passed (8 ms)
  • Your runtime beats 44.83 % of golang submissions
  • Your memory usage beats 86.21 % of golang submissions (9.8 MB)
  • 耗时 4:5:1

提升：

func getAllElements(root1 *TreeNode, root2 *TreeNode) []int {
	// 直接收集两个BST的中序遍历结果
	nums1 := inorderTraversal(root1)
	nums2 := inorderTraversal(root2)

	// 合并两个有序数组
	return mergeSortedArrays(nums1, nums2)
}

// 中序遍历 - 使用闭包避免全局变量
func inorderTraversal(root *TreeNode) []int {
	var result []int
	var traverse func(*TreeNode)

	traverse = func(node *TreeNode) {
		if node == nil {
			return
		}
		traverse(node.Left)
		result = append(result, node.Val)
		traverse(node.Right)
	}

	traverse(root)
	return result
}

// 合并两个有序数组
func mergeSortedArrays(nums1, nums2 []int) []int {
	m, n := len(nums1), len(nums2)
	result := make([]int, 0, m+n)
	i, j := 0, 0

	for i < m && j < n {
		if nums1[i] < nums2[j] {
			result = append(result, nums1[i])
			i++
		} else {
			result = append(result, nums2[j])
			j++
		}
	}

	// 添加剩余元素
	if i < m {
		result = append(result, nums1[i:]...)
	}
	if j < n {
		result = append(result, nums2[j:]...)
	}

	return result
}

Accepted#

  • 48/48 cases passed (1 ms)
  • Your runtime beats 89.66 % of golang submissions
  • Your memory usage beats 24.14 % of golang submissions (12.4 MB)