LeetCode-Go 题解精讲173. Binary Search Tree Iterator二叉搜索树迭代器的优先队列实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本题要求为二叉搜索树BST设计一个迭代器使其按升序从小到大逐个返回树中的节点值并支持 O(1) 平均时间复杂度的next()与hasNext()查询。本篇文章以 LeetCode-Go 仓库中 0173 题解文档 为主体结合仓库内的 源码实现、单元测试 与 通用二叉树数据结构完整还原遍历整棵树 最小堆按序弹出这一解题方案。读完本文你将掌握题目约束的准确含义、优先队列方案在 Go 中的落地写法含container/heap接口五件套的实现细节、复杂度边界以及如何在仓库中构造测试树并验证迭代器行为。题目回顾按升序迭代 BST 节点实现一个二叉搜索树迭代器使用 BST 的根节点进行初始化。每次调用next()返回 BST 中的下一个最小数。以文档给出的示例树为例根节点 9左子树 7→3右子树 15→20BSTIterator iterator new BSTIterator(root); iterator.next(); // return 3 iterator.next(); // return 7 iterator.hasNext(); // return true iterator.next(); // return 9 iterator.hasNext(); // return true iterator.next(); // return 15 iterator.hasNext(); // return true iterator.next(); // return 20 iterator.hasNext(); // return false题目还附带两条关键约束原文档 中均有注明next()和hasNext()应在平均 O(1) 时间内运行并使用 O(h) 内存其中 h 是树的高度可以假设调用next()时 BST 中一定存在下一个最小数即调用始终合法无需做空保护。题目本质上是把BST 中序遍历拆解成可暂停、可恢复的迭代式访问中序遍历恰好天然产生升序序列因此任何能模拟中序遍历进度的手段都可以作为迭代器实现。本文仓库采用的则是另一条等价路径——先完整收集节点再用最小堆按序吐出。解题思路优先队列方案题解文档 给出的解题思路非常简洁用优先队列解决即可。整体流程分三步在构造迭代器时通过一次遍历把 BST 中所有节点值收集到切片中将切片中所有值逐一Push进一个最小堆min-heap堆顶始终是当前最小值next()时弹出堆顶即为下一个最小数hasNext()用剩余元素计数判断。这里优先队列选取了 Go 标准库container/heap提供的最小堆语义Less(i, j)定义为pq[i] pq[j]堆顶恒为最小元素。于是迭代顺序天然就是升序无需额外排序。源码逐段精讲仓库中的完整实现位于 173. Binary Search Tree Iterator.go下面按职责拆解。1. 迭代器结构体与 TreeNode 别名package leetcode import ( container/heap github.com/halfrost/LeetCode-Go/structures ) // TreeNode define type TreeNode structures.TreeNode // BSTIterator define type BSTIterator struct { pq PriorityQueueOfInt count int }两点值得注意TreeNode通过类型别名直接复用仓库通用包structures中的定义Val int、Left *TreeNode、Right *TreeNode见 TreeNode.go全仓库 800 道题的树类题目共用同一份节点结构BSTIterator只维护两个字段最小堆pq和剩余节点数count。count承担了hasNext()的判空职责。小提示原题解文档中的 import 路径写作github.com/halfrost/leetcode-go/structures而仓库 go.mod 声明的模块名为github.com/halfrost/LeetCode-Go实际可编译的源码中均使用github.com/halfrost/LeetCode-Go/structures这一大小写形式。2. 构造函数后序遍历收集全部节点// Constructor173 define func Constructor173(root *TreeNode) BSTIterator { result, pq : []int{}, PriorityQueueOfInt{} postorder(root, result) for _, v : range result { heap.Push(pq, v) } bs : BSTIterator{pq: pq, count: len(result)} return bs } func postorder(root *TreeNode, output *[]int) { if root ! nil { postorder(root.Left, output) postorder(root.Right, output) *output append(*output, root.Val) } }构造函数分两步对应 源码第 28-36 行先用递归的postorder遍历把整棵树的节点值全部追加到result切片中。这个递归函数实际执行的是左 → 右 → 根的后序访问虽然访问顺序与中序不同但因为后续依赖堆来排序收集顺序并不影响最终结果再把result中的每个值通过heap.Push逐个压入最小堆。count记录节点总数供hasNext()使用。heap.Push会调用堆的Push方法追加元素并触发up上浮调整保证堆序不变。由于这里一次性灌入全部节点堆中始终保留所有待返回的值。3. next() 与 hasNext()最小堆的弹出与计数判空/** return the next smallest number */ func (this *BSTIterator) Next() int { this.count-- return heap.Pop(this.pq).(int) } /** return whether we have a next smallest number */ func (this *BSTIterator) HasNext() bool { return this.count ! 0 }Next()先递减count再调用heap.Pop弹出堆顶最小值并以int类型断言返回。heap.Pop内部会把堆顶与末尾元素交换、执行down下沉调整后取出末尾元素因此弹出的始终是当前最小数HasNext()仅判断count ! 0。由于构造函数中count初始化为节点总数且每次Next()都会自减因此该字段精确反映堆中剩余元素是否非空这也是文档中next()调用必然合法假设的代码化实现。4. PriorityQueueOfInt基于 heap.Interface 的最小堆type PriorityQueueOfInt []int func (pq PriorityQueueOfInt) Len() int { return len(pq) } func (pq PriorityQueueOfInt) Less(i, j int) bool { return pq[i] pq[j] } func (pq PriorityQueueOfInt) Swap(i, j int) { pq[i], pq[j] pq[j], pq[i] } func (pq *PriorityQueueOfInt) Push(x interface{}) { item : x.(int) *pq append(*pq, item) } func (pq *PriorityQueueOfInt) Pop() interface{} { n : len(*pq) item : (*pq)[n-1] *pq (*pq)[:n-1] return item }这一段源码第 63-131 行是container/heap的标准五件套实现任何一个基于heap.Interface的自定义堆都必须提供方法签名在本实现中的作用Lenint返回堆中元素个数Less(i, j int) bool定义堆序pq[i] pq[j]表示最小堆Swap(i, j int)交换两个下标处的元素Push(x interface{})追加元素到堆尾配合heap.Push自动上浮Popinterface{}弹出堆尾元素配合heap.Pop自动下沉注意Push与Pop必须使用指针接收者因为两者都要修改切片本身append/ 缩容这与仓库 structures/PriorityQueue.go 中PQ类型的实现风格一致而Less用比较保证堆顶恒为最小值。这里heap.Pop返回值经类型断言.(int)还原为整数与题目要求的int返回值吻合。复杂度分析实现与题目约束的差异题目最优约束是next()/hasNext()平均 O(1)、额外内存 O(h)。从上述源码结构看仓库这份优先队列实现的实际复杂度如下读者在面试中应能清晰陈述构造阶段一次后序遍历收集 n 个节点为 O(n)n 次heap.Push每次 O(log n)合计 O(n log n)next()heap.Pop为 O(log n)并非题目最优的 O(1)hasNext()O(1)仅比较count空间堆中保存全部 n 个节点值为 O(n)大于题目建议的 O(h)。也就是说这份实现以空间换简单实现极其直观、代码量小且能正确通过题目示例但它并不满足题目 Note 中平均 O(1) / O(h) 内存的最优指标。若面试中追求最优解通常采用显式栈模拟中序遍历、延迟展开左链的经典方案维护一个栈next()时不断把左子树压栈后弹出栈顶并转向右子树即可做到均摊 O(1) 的next()与 O(h) 的栈空间。仓库内 0173 目录当前仅收录了优先队列这一种实现本文不做虚构。测试验证结合测试文件复现示例流程仓库为本题提供了测试文件 173. Binary Search Tree Iterator_test.go核心片段func Test_Problem173(t *testing.T) { root : structures.Ints2TreeNode([]int{9, 7, 15, 3, structures.NULL, structures.NULL, 20}) obj : Constructor173(root) param1 : obj.Next() // 期望 3 param2 : obj.HasNext() // 期望 true param1 obj.Next() // 期望 7 param1 obj.Next() // 期望 9 param1 obj.Next() // 期望 15 param1 obj.Next() // 期望 20 param2 obj.HasNext() // 期望 false }测试复现了题目的标准流程测试树构造借助 TreeNode.go 中的Ints2TreeNode与NULL常量NULL -1 63将层序数组[9, 7, 15, 3, NULL, NULL, 20]还原为示例 BST——根 9左子 7其左子 3右子 15其右子 20迭代顺序断言依次Next()得到 3 → 7 → 9 → 15 → 20与题目给出的期望输出完全一致前四次HasNext()为 true最后一次为 false。该测试用例以打印运行轨迹为主fmt.Printf输出每次调用的返回值未使用t.Errorf做硬断言可从输出人工核对序列。仓库 gotest.sh 与 README 声称全部题解均配套测试0173 即为其一。小结LeetCode-Go 仓库对 173. Binary Search Tree Iterator 给出的答案是遍历全树 最小堆按序弹出Constructor173用后序遍历收集全部节点值通过container/heap最小堆维护升序Next()弹堆顶、HasNext()看计数。整个方案结构清晰、代码紧凑是理解 Go 标准库堆接口与迭代器设计的绝佳范例同时它也直观地展示了正确性与最优性之间的差异——题目 Note 要求 O(1)/O(h)而本实现为 O(log n)/O(n)读者可在掌握本方案后进一步探索显式栈的均摊 O(1) 写法做到对这道经典题的多解法融会贯通。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考