前言
持续更新了
正文
问题来源
本问题来自leetcode上的173题。
问题描述
实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
调用 next() 将返回二叉搜索树中的下一个最小的数。
示例 1:
BSTIterator iterator = new BSTIterator(root);
iterator.next(); // 返回 3
iterator.next(); // 返回 7
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 9
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 15
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 20
iterator.hasNext(); // 返回 false
分析：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type BSTIterator struct {
elements []int
i int
}
func visit(root *TreeNode, res *[]int) {
if root == nil {
return
}
visit(root.Left, res)
*res = append(*res, root.Val)
visit(root.Right, res)
}
func Constructor(root *TreeNode) BSTIterator {
res := BSTIterator{make([]int, 0), 0}
visit(root, &res.elements)
return res
}
/** @return the next smallest number */
func (this *BSTIterator) Next() int {
i := this.i
this.i++
return this.elements[i]
}
/** @return whether we have a next smallest number */
func (this *BSTIterator) HasNext() bool {
return this.i < len(this.elements)
}
/**
* Your BSTIterator object will be instantiated and called as such:
* obj := Constructor(root);
* param_1 := obj.Next();
* param_2 := obj.HasNext();
*/
总结：
勤思考。
结语
不管怎么样好好加油。
