LeetCode-173

题目

173. 二叉搜索树迭代器

结果

代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type BSTIterator struct {
	idx     int
	inorder []int
}

func Constructor(root *TreeNode) BSTIterator {
	itr := BSTIterator{inorder: []int{}}
	dfs(root, &itr)
	return itr
}

func (this *BSTIterator) Next() int {
	this.idx++
	return this.inorder[this.idx-1]
}

func (this *BSTIterator) HasNext() bool {
	return this.idx < len(this.inorder)
}

func dfs(root *TreeNode, itr *BSTIterator) {
	if root == nil {
		return
	}
	dfs(root.Left, itr)
	itr.inorder = append(itr.inorder, root.Val)
	dfs(root.Right, itr)
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * obj := Constructor(root);
 * param_1 := obj.Next();
 * param_2 := obj.HasNext();
 */