LeetCode-Go 题解 1305：两棵二叉搜索树的所有元素（BST 中序遍历 + 归并排序）

LeetCode-Go 题解 1305两棵二叉搜索树的所有元素BST 中序遍历 归并排序【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文基于开源仓库 LeetCode-GoLeetCode 的 Go 题解集中leetcode/1305.All-Elements-in-Two-Binary-Search-Trees一题的题解文档深入讲解「两棵二叉搜索树的所有元素」这道经典面试题。核心思路是利用 BST 中序遍历天然有序的特性将问题转化为合并两个有序数组从而把暴力解法 O((nm)log(nm)) 的时间复杂度优化到 O(nm)。读完本文你将掌握中序遍历 双指针归并的完整 Go 实现、两种解法的复杂度对比以及如何在本地运行仓库自带的测试用例进行验证。题目描述给定两棵二叉搜索树root1和root2返回一个列表其中包含两棵树中的所有整数并按升序排列。示例示例 1root1 [2,1,4]root2 [1,0,3]Input: root1 [2,1,4], root2 [1,0,3] Output: [0,1,1,2,3,4]示例 2root1 [0,-10,10]root2 [5,1,7,0,2]Input: root1 [0,-10,10], root2 [5,1,7,0,2] Output: [-10,0,0,1,2,5,7,10]示例 3其中一棵树为空root1 []root2 [5,1,7,0,2]Input: root1 [], root2 [5,1,7,0,2] Output: [0,1,2,5,7]示例 4另一棵树为空root1 [0,-10,10]root2 []Input: root1 [0,-10,10], root2 [] Output: [-10,0,10]示例 5两棵树均为非满二叉树root1 [1,null,8]root2 [8,1]Input: root1 [1,null,8], root2 [8,1] Output: [1,1,8,8]数据约束每棵树最多有5000个节点每个节点的值在[-10^5, 10^5]之间。解题思路把「两棵 BST」转化为「两个有序数组的合并」这一题最暴力、最简单的方法是把两棵树的节点全部遍历出来放到同一个数组里再整体从小到大排序。虽然这样也能通过AC但时间复杂度偏高——因为题目给出的「二叉搜索树」这一关键条件完全没有被利用上。BST二叉排序树有一个核心性质中序遍历结果一定是升序序列。因此题目真正的意图是考察「合并两个有序数组」这一经典算法对root1、root2分别做中根遍历inorder traversal得到两个有序数组使用双指针归并这两个有序数组一次扫描即可得到全局升序结果。这一步对应的正是 LeetCode 88. Merge Sorted Array 的归并思路而中序遍历本身则对应 LeetCode 94. Binary Tree Inorder Traversal。解法一中序遍历 合并有序数组推荐O(nm)仓库中的主解法getAllElements位于 1305. All Elements in Two Binary Search Trees.go完整代码如下// 解法一 合并排序 func getAllElements(root1 *TreeNode, root2 *TreeNode) []int { arr1 : inorderTraversal(root1) arr2 : inorderTraversal(root2) arr1 append(arr1, make([]int, len(arr2))...) merge(arr1, len(arr1)-len(arr2), arr2, len(arr2)) return arr1 }关键步骤拆解第 1 步中序遍历拿到有序数组。源码复用了第 94 题的inorderTraversal实现94. Binary Tree Inorder Traversal.go递归版实现为// this is 94 solution func inorderTraversal(root *TreeNode) []int { var result []int inorder(root, result) return result } func inorder(root *TreeNode, output *[]int) { if root ! nil { inorder(root.Left, output) *output append(*output, root.Val) inorder(root.Right, output) } }递归顺序是「左子树 → 根节点 → 右子树」因此arr1、arr2天然都是升序数组。值得注意的是inorder通过*output append(...)将结果写回调用方持有的切片这是 Go 中在递归中累积结果的标准写法——因为append可能触发底层数组扩容必须把新切片赋值回原指针否则外层拿到的仍是旧切片。第 2 步预分配归并目标空间。arr1 append(arr1, make([]int, len(arr2))...)在arr1尾部追加len(arr2)个占位元素使arr1的容量足够容纳两个数组合并后的全部元素。这正好模拟了第 88 题「合并两个有序数组」中nums1尾部预留了mn空间的输入前提。第 3 步原地归并。复用第 88 题的merge实现88. Merge Sorted Array.go采用从后往前的双指针写法// this is 88 solution func merge(nums1 []int, m int, nums2 []int, n int) { if m 0 { copy(nums1, nums2) return } i : m - 1 j : n - 1 k : m n - 1 // 从后面往前放只需要循环一次即可 for ; i 0 j 0; k-- { if nums1[i] nums2[j] { nums1[k] nums1[i] i-- } else { nums1[k] nums2[j] j-- } } for ; j 0; k-- { nums1[k] nums2[j] j-- } }归并的要点在于i、j分别从两个有序数组的末尾开始k指向合并后数组的末尾每次取nums1[i]与nums2[j]中较大者填入nums1[k]从尾部向前填充可以避免覆盖nums1中尚未处理的元素一趟循环即可完成循环结束后若nums2还有剩余则整体copy到nums1头部nums1剩余部分本身已就位无需处理边界情况m 0第一棵树为空时直接copy对应题目示例 4root1 []时输出就是root2的中序序列。复杂度分析时间复杂度O(n m)。中序遍历两棵树各一次归并一趟均为线性扫描其中 n、m 分别为两棵树的节点数。空间复杂度O(n m)两个有序数组与递归栈所需空间。解法二暴力遍历 整体排序能 AC 但时间复杂度高仓库同时提供了第二种解法getAllElements1用于对比说明// 解法二 暴力遍历排序时间复杂度高 func getAllElements1(root1 *TreeNode, root2 *TreeNode) []int { arr : []int{} arr append(arr, preorderTraversal(root1)...) arr append(arr, preorderTraversal(root2)...) sort.Ints(arr) return arr }它先做前序遍历把两棵树的节点值全部收集到同一个切片中preorderTraversal复用第 144 题的实现位于同一源码文件中再调用sort.Ints整体排序。该解法没有利用 BST 有序性时间复杂度为 O((nm)log(nm))当两棵树各有 5000 个节点上限时性能差距会相当明显。因此仓库题解明确将其标注为「时间复杂度高」仅作为正确性参考。测试用例验证本地运行 1305 题测试仓库为每一道题都配套了表驱动测试1305 题的测试位于 1305. All Elements in Two Binary Search Trees_test.go把题目给出的 5 组示例全部固化为用例qs : []question1305{ { para1305{[]int{2, 1, 4}, []int{1, 0, 3}}, ans1305{[]int{0, 1, 1, 2, 3, 4}}, }, { para1305{[]int{0, -10, 10}, []int{5, 1, 7, 0, 2}}, ans1305{[]int{-10, 0, 0, 1, 2, 5, 7, 10}}, }, { para1305{[]int{}, []int{5, 1, 7, 0, 2}}, ans1305{[]int{0, 1, 2, 5, 7}}, }, { para1305{[]int{0, -10, 10}, []int{}}, ans1305{[]int{-10, 0, 10}}, }, { para1305{[]int{1, structures.NULL, 8}, []int{8, 1}}, ans1305{[]int{1, 1, 8, 8}}, }, }测试中通过structures.Ints2TreeNode把层序数组还原成二叉树其中structures.NULL定义为-1 63用于表示空节点构造逻辑见 structures/TreeNode.go 中的Ints2TreeNode与NULL常量。运行测试的方式# 运行单个题目在仓库根目录下 go test -v -run Test_Problem1305 ./leetcode/1305.All-Elements-in-Two-Binary-Search-Trees/ # 或运行全部题目测试 go test ./leetcode/...仓库根目录的 gotest.sh 还提供了全量覆盖率统计命令go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...该项目坚持「100% test coverage」的工程实践每个题解都配有对应的表驱动测试阅读 README.md 可以了解仓库的整体组织方式。小结核心考点利用BST 中序遍历有序的性质把「两棵 BST 合并排序」降维成「两个有序数组合并」最优解法中序遍历 从后往前双指针归并时间复杂度 O(nm)空间复杂度 O(nm)复用了两道经典题的实现中序遍历第 94 题与合并有序数组第 88 题代码见 1305. All Elements in Two Binary Search Trees.go测试见 1305. All Elements in Two Binary Search Trees_test.go暴力解法收集 sort.Ints虽能 AC但在节点数达 5000 上限时性能明显劣势仅适合作为对照实现。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考